[baekjoon] 백준 4963번(파이썬): 섬의 개수

문제

4963번: 섬의 개수

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

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

- 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.

- 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

- 입력은 여러 개의 테스트 케이스로 이루어져 있다.

- 각 테스트 케이스의 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

-  h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

- 입력의 마지막 줄에는 0이 두 개 주어진다.

알고리즘

- dfs 탐색으로 문제를 수행한다.

- 이전에 풀었던 dfs 문제와 다르게 대각선 위치들도 재귀적으로 탐색한다.

코드

import sys
sys.setrecursionlimit(10**6) # 재귀 허용 깊이를 수동으로 늘려주는 코드


# dfs 탐색
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False

    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 1:
        # 해당 노드 방문 처리
        graph[x][y] = 0
        # 상, 하, 좌, 우, 대각선의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        dfs(x + 1, y + 1)
        dfs(x - 1, y - 1)
        dfs(x + 1, y - 1)
        dfs(x - 1, y + 1)

        return True
    return False


# 테스트 케이스만큼 반복
while True:
    m, n = map(int, sys.stdin.readline().split())

    if m == 0 and n == 0:
        break

    # 각 노드가 연결된 정보를 표현
    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    cnt = 0
    
    # 현재 위치에서 DFS 수행
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                dfs(i,j)
                cnt += 1

    print(cnt)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법