백준 4963 | 섬의 개수 (DFS)

문제 출처 : https://www.acmicpc.net/problem/4963

문제

• 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
  

• 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

• 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
• 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.

문제 접근 방법

• 한 정사각형에서 가로, 세로 또는 대각선으로 연결되어 있는 사각형 → 8 방향을 방문하는 DFS로

코드

import sys

# 런타임 에러 (RecursionError)
sys.setrecursionlimit(5000)


def input():
    return sys.stdin.readline().rstrip()


def dfs(x, y):
    global answer, graph
    graph[x][y] = 0
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < m and 0 <= ny < n:
            if graph[nx][ny]:
                dfs(nx, ny)


# 상,하, 좌, 우, 대각선 4방향(왼쪽 위, 왼쪽 아래, 오른쪽 아래, 오른쪽 위)
dx, dy = (-1, 1, 0, 0, -1, 1, 1, -1), (0, 0, -1, 1, -1, -1, 1, 1)

while True:
    answer = 0
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break

    graph = [[] for _ in range(m)]
    for i in range(m):
        graph[i] = list(map(int, input().split()))

    for i in range(m):
        for j in range(n):
            if graph[i][j]:
                dfs(i, j)
                answer += 1

    print(answer)