[백준] 4963. 섬의 개수

문제 링크

문제 설명

전체 맵에서 연결된 섬의 개수를 카운트하는 문제로 그래프 탐색으로 문제를 해결할 수 있다. 전체 노드를 탐색하면서 연결된 노드를 재귀방식으로 계속 탐색하고 최종적으로 더 이상 연결된 섬이 없을 때 True 값을 반환하여 개수를 카운트하는 dfs방식으로 접근해봤다.

문제 상황

다음과 같이 코드를 작성했는데 [런타임 에러 (RecursionError)] 발생했다. 8방향으로 섬(1인 값)인지 확인하기 때문에 재귀 호출이 너무 많은 것 같다고 판단.

인터넷에서 찾아본 결과 파이썬 자체에서 재귀호출할 수 있는 max값이 정해져있어 sys.setrecursionlimit(10 ** 6) 코드를 추가해 해당 값을 임의로 설정했다.

하지만, 이번에는 틀렸다고 결과가 나왔다.

코드

# 섬의 개수  
import sys  
  
read = sys.stdin.readline  
sys.setrecursionlimit(10 ** 6)  
  
  
def dfs(x, y):  
    if x < 0 or x >= h or y < 0 or y >= w:  
        return False   
    if graph[x][y] == 1:  
        graph[x][y] = 0  
        dfs(x - 1, y - 1)  
        dfs(x, y - 1)  
        dfs(x + 1, y - 1)  
        dfs(x - 1, y)  
        dfs(x + 1, y)  
        dfs(x - 1, y + 1)  
        dfs(x, y + 1)  
        dfs(x + 1, y + 1)  
        return True  
    return False  
  
while True:  
    w, h = map(int, read().split())  
  
    if w == 0 and h == 0:  
        break  
    graph = []  
    for i in range(h):  
        graph.append(list(map(int, read().split())))  
  
    result = 0  
  
    for i in range(w):  
        for j in range(h):  
            if dfs(i, j):  
                result += 1  
  
    print(result)

해결 방법

결론은,,, 재귀 호출 자체를 하지 않도록 코드를 짜야한다는 것이였다.
위에서 정의한 dfs 메서드를 보면 일단 dfs함수를 호출하고 해당 위치의 값이 전체 범위를 벗어났는지 혹은 섬(1)이 아닌지를 판단하여 False를 반환하는데 이 과정 자체를 조건문으로 필터링하여 호출되는 경우 자체를 줄여야한다.

def dfs(x, y):  
    if x < 0 or x >= h or y < 0 or y >= w:  
        return False   
    if graph[x][y] == 1:  
        graph[x][y] = 0  
        dfs(x - 1, y - 1)  
        dfs(x, y - 1)  
        dfs(x + 1, y - 1)  
        dfs(x - 1, y)  
        dfs(x + 1, y)  
        dfs(x - 1, y + 1)  
        dfs(x, y + 1)  
        dfs(x + 1, y + 1)  
        return True  
    return False  

코드

# 섬의 개수  
import sys  
  
read = sys.stdin.readline  
sys.setrecursionlimit(10 ** 6)  
  
dx = [-1, 0, 1, -1, 1, -1, 0, 1]  
dy = [-1, -1, -1, 0, 0, 1, 1, 1]  
  
def dfs(x, y):  
    graph[x][y] = 0  
    for i in range(8):  
        nx = x + dx[i]  
        ny = y + dy[i]  
        if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:  
            dfs(nx, ny)  
  
  
while True:  
    w, h = map(int, read().split())  
  
    if w == 0 and h == 0:  
        break  
    graph = []  
    for i in range(h):  
        graph.append(list(map(int, read().split())))  
  
    result = 0  
  
    for i in range(h):  
        for j in range(w):  
            if graph[i][j] == 1:  
                dfs(i, j)  
                result += 1  
  
    print(result)

dfs

이와 같이 외부에서 조건문으로 필터링하여 재귀호출 자체가 수행되지 않게 하도록함

if graph[i][j] == 1:  
		dfs(i, j)  
		result += 1 

...

def dfs(x, y):  
    graph[x][y] = 0  
    for i in range(8):  
        nx = x + dx[i]  
        ny = y + dy[i]  
        if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:  
            dfs(nx, ny)  

결론 및 피드백

• 일반적으로 재귀호출을 통해 구현하는 dfs보다 queue를 사용하여 구현하는 bfs를 먼저 생각해보자
  • 왜냐하면, 상대적으로 더 빠르게 코드가 동작한다.
• 문제와 별개로 x, y 값이 2차우너 배열에서 문제에서 w,h 값 중 어떤 것인지 종종 헷갈리는 상황을 발견했다. 로직이 맞더라도 반복문을 잘못 작성하면 문제가 생길 수 있기 때문에 유의해야 할 것 같다.