[Algorithm] 백준 2667번: 단지 번호 붙이기 | DFS, BFS 비교

문제 출처: https://www.acmicpc.net/problem/2667

---

1. 결과

1) BFS 이용: 메모리 32108KB, 시간 96ms

2) DFS 이용: 메모리 29304KB, 시간 76ms

2. 풀이

이 문제는 전형적인 그래프 탐색 문제이다. 그래프 탐색은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 두 가지가 있는데, 비교적 간단한 문제는 두 방법 모두 가능하다. 여기서 잠깐 둘의 차이를 짚고 가면, BFS는 최적, 최단과 같은 요소를 구할 때 유용하고, DFS는 특정 경로나 요소에 대해 끝까지 경우를 끝까지 탐색해볼 때 유용하다. 그런 부분에서 이 문제는 DFS가 더 적합하다고 볼 수 있다. 특정 영역에 대해 끝까지 탐색한 넓이를 구하는 것이기 때문이다. 위의 결과에서도 알 수 있듯이 메모리와 시간 모두 DFS가 조금은 유리하다는 것을 알 수 있다.

BFS는 한 지점에서 주변 네 방향에 대해 모든 좌표를 탐색한 후, 적합하다고 생각하면 일단 다음에 둘러볼 위치를 저장하는 큐에 저장한다. 그리고 큐에 있는 다음 위치 중 하나에 대해 다시 같은 것을 반복한다. 이런 식으로 한 지점, 한 지점마다 4방향 모두 탐색하고 넓이를 저장한다면, DFS는 한 지점에 대해 갈 수 있는 지점을 바로 탐색한다. 그리고 가능한 다음 지점을 또 탐색하고, 이런 식으로 한 위치에 대해 가능한 모든 지점을 곧바로 탐색하기 때문에 조금은 더 빠른 것 같다.

BFS는 보통 큐, 덱을 통해 구현하고, DFS는 스택, 재귀 호출로써 구현할 수 있다. 아래 코드는 각각 덱, 재귀 호출로 구현한 코드이다. 앞으로 다른 그래프 탐색 문제에서는 BFS, DFS의 차이를 인식하고 각 문제에 따라 적합한 방법을 선택하고 구현할 수 있도록 문제와 풀이를 이해해보며 푸는 것이 좋을 것 같다고 생각한다.

import sys
from collections import deque

# BFS 이용한 코드(deque) - 32108KB, 96ms
def bfs(board, n, position, visited):
    dr = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)]
    area = 0
    q = deque([position])

    while q:
        x, y = q.popleft()
        for xx, yy in dr:
            if 0 <= x+xx < n and 0 <= y+yy < n and board[x+xx][y+yy] and not visited[x+xx][y+yy]:
                q.append([x+xx, y+yy])
                visited[x+xx][y+yy] = True
                area += 1
    
    return area

# DFS 이용한 코드(재귀 호출) - 29304KB, 76ms
def dfs(board, n, position, visited):
    dr = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)]
    area = 0
    x, y = position
    
    for dx, dy in dr:
        if 0 <= x+dx < n and 0 <= y+dy < n and board[x+dx][y+dy] and not visited[x+dx][y+dy]:
            visited[x+dx][y+dy] = True
            area += 1
            area += dfs(board, n, [x+dx, y+dy], visited)
    
    return area

def main():
    N = int(sys.stdin.readline())
    board = [list(map(int, list(sys.stdin.readline().strip()))) for _ in range(N)]
    visited = [[False] * N for _ in range(N)]
    result = []
    cnt = 0
    
    for i in range(N):
        for j in range(N):
            if not board[i][j] or visited[i][j]: continue
            # result.append(bfs(board, N, [i, j], visited))  # BFS - 32108KB, 96ms
            result.append(dfs(board, N, [i, j], visited))  # DFS - 29304KB, 76ms
            cnt += 1

    return [cnt] + sorted(result)

if __name__ == "__main__":
    for i in main():
        print(i)