4963 - 섬의 개수

풀이

DFS(깊이 우선 탐색)을 이용하여 풀 수 있다.
주의해야 할 점이
앞 뒤 양 옆으로 이어진 섬만이 같은 섬으로 계산하는게 아니라
대각선으로 이동할 수 있는 섬들도 같은 섬으로 계산을 해야한다
그렇게 이동하기 위해서
dx = [1, -1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
으로 설정을 하였다.

소스코드

import sys


def dfs(x, y):
    visited[x][y] = True

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0<= nx < h) and (0 <= ny < w):
             if (visited[nx][ny] == False) and (graph[nx][ny] == 1):
                 dfs(nx, ny)


dx = [1, -1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
while 1:
    w, h = map(int, input().split())
    graph = []
    visited = [[False for i in range(w)] for j in range(h)]
    count = 0
    if (w == 0 and h == 0):
        break
    for i in range(h):
        geo = list(map(int, input().split()))
        graph.append(geo)
    for i in range(h):
        for j in range(w):
            if graph[i][j] and visited[i][j] == False:
                dfs(i, j)
                count += 1
    print(count)