[Python Algorithm] 섬의 개수 BOJ #4963

문제

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

4963번: 섬의 개수

 

내 문제 풀이

import sys
sys.setrecursionlimit(10000)

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0:
        break

    space = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]
    dx = [0, 0, -1, 1, -1, 1, -1, 1]
    dy = [-1, 1, 0, 0, -1, 1, 1, -1]
    count = 0

    def dfs(x, y):
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= h or ny >= w or space[nx][ny] == 0: continue

            space[nx][ny] = 0
            dfs(nx, ny)

    for i in range(h):
        for j in range(w):
            if space[i][j] == 1:
                count += 1
                space[i][j] = 0
                dfs(i, j)

    print(count)

👉 DFS 문제로, 이어진 섬들을 한 번에 체크해주는 것이 포인트 !

• 주어진 지도 space 리스트를 순차적으로 돌면서 1이 등장하면
  그 자리를 0으로 바꿔주고, count를 증가시킨 후 dfs 함수를 호출했다.
• dfs 함수에서는 상하좌우, 그리고 대각선까지 총 8곳을 탐색했고
  1을 발견하면 그 자리를 0으로 바꿔주고, 또 그 주변을 탐색하게 했다.
  이어진 모든 섬이 0으로 바뀌면 dfs 함수는 종료된다.
• 이렇게 이어진 섬들을 모두 0으로 바꾼 뒤, 다시 또 다른 섬이 있는지 찾는다.

 

💡 피드백

• 굉장히 쉽고, 굉장히 전형적인,,! DFS 문제였다.
• sys.setrecursionlimit을 해주지 않으면 런타임 에러가 나더라. 꼭 해주세용