[백준 4963 파이썬] - 섬의 개수

📌 문제

💯 정답

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)        # 무한 재귀호출 방지

# 상,하,좌,우 뿐만 아니라 대각선도 추가
def dfs(x, y):
    if x < 0 or x >= w or y < 0 or y >= h:
        return False
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        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:
    h, w = map(int, input().split())
    if w == 0 and h == 0:
        break
    # 2차원 리스트의 맵 정보 입력
    graph = []
    for i in range(w):
        graph.append(list(map(int, input().split())))
    cnt = 0
    for i in range(w):
        for j in range(h):
            if dfs(i, j) == True:
                cnt += 1
    print(cnt)

📝 설명

• 파이썬은 재귀 깊이가 정해져 있어 의도적으로 늘려주는 과정이 있어야 한다.
  "sys.setrecursionlimit(10000)" 를 사용함으로써 무한 재귀 호출을 방지한다.
  
• 이 문제는 <이코테>에서 배운 dfs 로직을 활용해 풀었는데 계속 런타임 에러가 떴다.

• 첫번째 이유는 위에 적은 것과 같이 setrecursionlimit을 사용하지 않았기 때문이고

• 두번째 이유는 w, h를 잘못 이해했기 때문이다.
• w는 너비 h는 높이 이므로 결구 w가 열 h가 행 임을 알 수 있다.
• 따라서 h, w의 위치를 바꾸어 입력 받았더니 문제가 해결됐다.
• 하지만 생각해보니 저렇게하면 행렬이 90도 회전된 상태가 되기때문에 이 문제에서는 괜찮았으나 다른 방법을 사용해야 할 것 같다.

⭐️ 알고가기

👉 [파이썬] - 재귀 문제의 sys.setrecursionlimit