백준 2667번: 단지번호 붙이기(bfs)

2024.12.12 - [알고리즘/백준] - 백준 2667번: 단지 번호 붙이기

백준 2667번: 단지 번호 붙이기

이전 글에서는 DFS로 문제를 해결했지만, 이번에는 BFS로 접근해 보았습니다.

DFS와 BFS가 모두 사용 가능한 이유

이 문제에서 DFS와 BFS가 모두 가능한 이유는 다음과 같습니다:

• 탐색 범위가 제한적: 문제의 입력 크기가 작기 때문에 DFS와 BFS 모두 메모리나 시간 면에서 무리 없이 동작합니다.
• 그래프 구조가 단순함: 상하좌우로 연결된 집만 탐색하면 되므로 복잡한 탐색 로직이 필요하지 않습니다.
• 최단 경로 탐색이 불필요: 단지 내 집의 수를 세는 것이 목표이므로, 탐색 순서가 중요하지 않습니다.

DFS가 적합한 경우

• 탐색 경로의 깊이가 중요한 경우: 예를 들어, 미로 탐색처럼 특정 경로를 끝까지 탐색해야 하는 경우.
• 재귀적으로 구현하기 쉬운 경우: 연결된 구성 요소를 재귀적으로 탐색하는 문제에 적합합니다.

BFS가 적합한 경우

• 최단 거리 탐색이 필요한 경우: BFS는 계층적으로 탐색하기 때문에 최단 경로를 구할 때 효율적입니다.
• 메모리 관리가 중요한 경우: BFS는 재귀 호출을 사용하지 않으므로 스택 깊이 제한이 없고 큐를 이용해 관리하기 쉽습니다.

BFS로 단지 번호 붙이기 구현

다음은 BFS를 사용한 단지 번호 붙이기 문제 해결 코드입니다

from collections import deque
import sys

# 입력을 빠르게 받기 위해 sys.stdin.readline을 사용합니다.
input = sys.stdin.readline

# 네 방향(상, 하, 좌, 우)으로 이동하기 위한 델타 값
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS를 사용하여 연결된 컴포넌트의 크기를 계산하는 함수
def bfs(graph, visited, height, width):
    # BFS를 위한 큐를 생성하고 시작 위치를 추가
    queue = deque([(height, width)])
    # 방문 처리
    visited[height][width] = 1
    # 현재 컴포넌트의 크기를 저장
    c = 1
    
    # 큐가 빌 때까지 반복
    while queue:
        y, x = queue.popleft()
        # 네 방향으로 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 좌표가 유효하고, 아직 방문하지 않았으며, 값이 1인 경우
            if 0 <= nx < len(graph[0]) and 0 <= ny < len(graph):
                if graph[ny][nx] == 1 and visited[ny][nx] == 0:
                    queue.append((ny, nx))  # 다음 탐색을 위해 큐에 추가
                    visited[ny][nx] = 1  # 방문 처리
                    c += 1  # 컴포넌트 크기 증가

    return c

# 테스트 케이스 수(배열 크기) 입력
tc = int(input())
# 행렬 입력
graph = [list(map(int, input().strip())) for i in range(tc)]
# 방문 여부를 저장하는 2차원 배열
visited = [[0 for i in range(tc)] for j in range(tc)]
# 각 컴포넌트의 크기를 저장할 리스트
lst = []

# 모든 셀을 순회하며 BFS 실행
for i in range(tc):
    for j in range(tc):
        # 값이 1이고 아직 방문하지 않았다면 BFS 실행
        if graph[i][j] == 1 and visited[i][j] == 0:
            lst.append(bfs(graph, visited, i, j))

# 총 컴포넌트 수 출력
print(len(lst))
# 각 컴포넌트의 크기를 정렬하여 출력
for i in sorted(lst):
    print(i)

 

참고로 DFS에서는 재귀 호출로 count를 계산했지만, BFS에서는 큐와 반복문을 통해 count를 직접 증가시키는 방식으로 구현하였습니다.

1. 첫 번째 BFS 시작 (0, 1)

• 초기 큐 상태: [(0, 1)]
• 탐색 과정:
  1. 큐에서 (0, 1) 꺼냄 → 추가: (0, 2), (1, 1)
  2. 큐에서 (0, 2) 꺼냄 → 추가: (1, 2)
  3. 큐에서 (1, 1) 꺼냄 → 추가: (2, 0)
  4. 큐에서 (1, 2) 꺼냄 → 추가: (2, 1)
  5. 큐에서 (2, 0) 꺼냄 → 추가: (2, 2)
  6. 큐에서 (2, 1) 꺼냄 → 추가 없음
  7. 큐에서 (2, 2) 꺼냄 → 추가 없음
• 컴포넌트 크기: 7

0110000
0110000
1110000
0000000
0000000
0000000
0000000

2. 두 번째 BFS 시작 (3, 4)

• 초기 큐 상태: [(3, 4)]
• 탐색 과정:
  1. 큐에서 (3, 4) 꺼냄 → 추가: (3, 5), (4, 4)
  2. 큐에서 (3, 5) 꺼냄 → 추가: (3, 6)
  3. 큐에서 (4, 4) 꺼냄 → 추가: (4, 5)
  4. 큐에서 (3, 6) 꺼냄 → 추가 없음
  5. 큐에서 (4, 5) 꺼냄 → 추가: (4, 6), (5, 5)
  6. 큐에서 (4, 6) 꺼냄 → 추가 없음
  7. 큐에서 (5, 5) 꺼냄 → 추가: (5, 6)
  8. 큐에서 (5, 6) 꺼냄 → 추가 없음
• 컴포넌트 크기: 8

0110000
0110000
1110000
0000111
0000111
0000011
0000000

3. 세 번째 BFS 시작 (5, 1)

• 초기 큐 상태: [(5, 1)]
• 탐색 과정:
  1. 큐에서 (5, 1) 꺼냄 → 추가: (5, 2)
  2. 큐에서 (5, 2) 꺼냄 → 추가: (6, 1), (5, 3)
  3. 큐에서 (6, 1) 꺼냄 → 추가: (6, 2)
  4. 큐에서 (5, 3) 꺼냄 → 추가: (5, 4)
  5. 큐에서 (6, 2) 꺼냄 → 추가: (6, 3)
  6. 큐에서 (5, 4) 꺼냄 → 추가 없음
  7. 큐에서 (6, 3) 꺼냄 → 추가 없음
• 컴포넌트 크기: 9

0110000
0110000
1110000
0000111
0100111
0111110
0111000