[99클럽 코테 스터디 6일차 TIL bfs/dfs] 백준 4963 섬의 개수 python

오늘의 학습 키워드

bfs/dfs

공부한 내용 본인의 언어로 정리하기

문제

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

코드

import sys
sys.setrecursionlimit(10000)

w, h = map(int, input().split())

while w != 0 and h != 0:
    count = 0
    island = []
    for _ in range(h):
        island.append(list(map(int, input().split())))
    visited = [[0] * w for i in range(h)]
    def dfs(x, y):
        visited[y][x] = 1
        for a, b in [(1, 0), (-1, 0), (0, 1), (0, -1), (-1, -1), (1, 1), (-1, 1), (1, -1)]:
            nx, ny = x + a, y + b
            if 0 <= nx < w and 0 <= ny < h and island[ny][nx] == 1:
                if visited[ny][nx] == 0:
                    dfs(nx, ny)
    for y in range(h):
        for x in range(w):
            if island[y][x] == 1 and visited[y][x] == 0:
                dfs(x, y)
                count += 1

    print(count)
    w, h = map(int, input().split())

 

해당 문제는 여러개의 테스트 케이스로 이루어져 있고, 해당 테스트 케이스의 종료 조건이 마지막에 0, 0이 나오는 경우였다. 따라서 while문을 통해 두 개의 값이 0, 0이 나올 때까지 입력을 계속 받아 케이스별로 계산을 처리해주었다.

해당 문제는 상, 하, 좌, 우, 대각선으로 연결된 1 들의 모임을 한 섬으로 치므로,  [(1, 0), (-1, 0), (0, 1), (0, -1), (-1, -1), (1, 1), (-1, 1), (1, -1)]를 통해 나올 수 있는 모든 경우를 세어 주었다. 또한 옆으로 계속 진행하는 넓이 탐색보다는 한 섬에서 1로 연결되어있는 다른 점을 찾는 것이기 때문에 재귀를 사용하는 dfs를 통해 문제를 해결하였다. 이후 한 탐색이 끝날 때 마다 count += 1을 더해 섬의 갯수를 셀 수 있었다.

 

오늘의 회고

처음에 코드를 제출했더니 Recursion Error가 발생했다. Recursion Error가 자주 발생하기에 해당 내용에 대해 정리해보았다.

Recursion Error란?

RecursionError는 파이썬에서 재귀 호출이 너무 많이 일어나서 최대 재귀 깊이(maximum recursion depth) 를 초과했을 때 발생하는 에러이다. 

RecursionError가 발생하는 이유

1. 기저 조건(base case) 이 없거나 잘못 정의되어 있어서, 함수가 끝나지 않고 무한히 자기 자신을 호출할 때 발생
2. 너무 많은 재귀가 필요한 문제를 풀고 있어서 파이썬의 기본 재귀 제한(기본값: 약 1000)을 넘었을 때도 발생

Recursion Error 해결 방법

 1. 기저 조건(Base Case) 확인

재귀 함수에는 반드시 종료 조건이 있어야 함으로 조건이 빠졌거나 잘못 작성되었는지 확인

 

 

 2. 재귀 깊이 제한 늘리기 (일시적 해결책) -> 해당 방법 사용

기저 조건은 정확하지만 문제 자체가 너무 큰 경우에는 sys.setrecursionlimit()을 사용해서 최대 깊이 늘리기

import sys
sys.setrecursionlimit(10000)

다만, 무한 재귀의 문제를 해결하지는 못하므로 기저 조건이 정확히 있는 경우에만 사용

 

3. 반복문으로 바꾸기

재귀 대신 반복문(loop) 으로 구현하면 RecursionError 없이 처리 가능

 

 

작년에는 실버5도 겨우겨우 풀던 내가 최근 bfs/dfs 문제를 자주 풀며 해당 유형이 나와도 익숙하게 처리하는 모습에 뿌듯했다..!! 1일 1코테를 통해 골드1, 플래티넘으로 가는 그날까지 열심히 해야지!!