[백준] 4963번 섬의 개수 _ 문제 풀이

 


1. 문제

https://www.acmicpc.net/problem/4963

2. 풀이

dfs 를 이용하여 문제를 해결해주었습니다. 8방향 모두를 확인하면서 문제를 해결해야합니다.

import sys
sys.setrecursionlimit(10**4)
# 상, 상우, 우, 우하, 하, 좌하, 좌, 좌상
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 1, 1, 1, 0, -1, -1, -1]
def dfs(w, h, maps, is_visited, r, c):
    if is_visited[r][c] or maps[r][c] == 0:
        return
    is_visited[r][c] = True
    for i in range(8):
        n_r, n_c = r + dr[i], c + dc[i]
        if 0 <= n_r < h and 0 <= n_c < w:
            dfs(w, h, maps, is_visited, n_r, n_c)

while True:
    island_num = 0
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    maps = [list(map(int, input().split())) for _ in range(h)]
    is_visited = [[False for _ in range(w)] for _ in range(h)]
    for r in range(h):
        for c in range(w):
            if is_visited[r][c] or maps[r][c] == 0:
                continue
            dfs(w, h, maps, is_visited, r, c)
            island_num += 1
    print(island_num)