너비 우선 탐색(Breath-First Search, BFS)은 그래프나 트리 탐색의 한 방법으로, 시작 정점에서 인접한 정점들을 먼저 방문하고, 그 다음 인접한 정점들 중 아직 방문하지 않은 정점들을 방문하는 방식입니다. 경우에 따라 최단 경로 탐색 알고리즘으로도 사용됩니다. 오늘은 BFS의 기초 개념과 함께 깊이 있는 문제 풀이를 진행해보겠습니다.
문제: 단지번호붙이기
문제 설명
주어진 n x n 크기의 0과 1로 구성된 배열에서 1은 집이 있는 곳을 의미하고 0은 집이 없는 곳을 의미합니다. 모든 집의 단지를 구별하기 위하여 각 단지에 고유한 번호를 붙이는 프로그램을 작성하십시오. 단지의 크기는 각 단지에 속한 집의 수로 정의됩니다.
입력
n (1 ≤ n ≤ 25) 0 또는 1로 구성된 n x n 배열
출력
각 단지의 크기를 오름차순으로 출력
예제 입력
7 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
예제 출력
1 7
문제 접근법
이 문제를 해결하기 위해 BFS 알고리즘을 이용하여 그래프를 탐색할 것입니다. 입력된 2차원 배열을 순회하며 각 집(1)을 만나면 BFS를 통해 연결된 모든 집의 수를 세어 단지의 크기를 계산합니다. 다음 단계에서 BFS의 개념을 자세히 설명하겠습니다.
너비 우선 탐색(BFS) 개념
BFS는 큐를 이용하여 구현됩니다. 다음 프로세스를 따릅니다:
- 시작 노드를 큐에 추가하고 방문 표시를 합니다.
- 큐에서 노드를 꺼내고 그 노드에 인접한 모든 노드(아직 방문하지 않은)들을 큐에 추가하고 방문 표시를 합니다.
- 큐가 비어있지 않으면 2번으로 돌아갑니다.
코딩 구현
BFS 알고리즘을 적용하여 문제를 해결하는 코드를 작성하겠습니다.
from collections import deque
def bfs(x, y, n, graph, visited):
queue = deque()
queue.append((x, y))
visited[x][y] = True
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
size = 1 # 단지의 크기를 저장
while queue:
cx, cy = queue.popleft() # 현재 위치
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] == 1:
visited[nx][ny] = True
queue.append((nx, ny))
size += 1 # 연결된 집의 수를 증가
return size # 단지의 크기 반환
def find_complexes(n, graph):
visited = [[False] * n for _ in range(n)]
complexes = []
for i in range(n):
for j in range(n):
if graph[i][j] == 1 and not visited[i][j]:
size = bfs(i, j, n, graph, visited)
complexes.append(size)
return sorted(complexes) # 크기를 오름차순으로 반환
# 예제 입력
n = 7
graph = [
[0, 0, 1, 0, 0, 1, 1],
[0, 0, 1, 0, 1, 1, 1],
[0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[1, 1, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]
]
complex_sizes = find_complexes(n, graph)
print(len(complex_sizes)) # 단지의 수 출력
for size in complex_sizes:
print(size) # 각 단지의 크기 출력
코드 설명
위 코드는 BFS를 이용하여 단지의 크기를 계산하는 방법을 보여줍니다. 주요 함수는 find_complexes와 bfs입니다.
bfs(x, y, n, graph, visited): 시작 점 (x, y)에서 BFS를 실행하여 해당 단지의 크기를 계산합니다. 큐를 이용하여 방문한 각 집을 기록하며 연결된 집을 모두 집계합니다.find_complexes(n, graph): 주어진 그래프를 순회하며 집(1)을 찾아 BFS를 호출하고, 계산된 단지 크기를 리스트에 저장합니다.
결론
너비 우선 탐색(BFS)은 유용한 탐색 방법으로, 다양한 분야에서 활용될 수 있습니다. 이번 강좌를 통해 BFS의 활용으로 문제를 해결하는 방법을 배웠기를 바랍니다. 문제 풀이과정에서의 코드 이해와 활용이 여러분의 코딩테스트에서도 큰 도움이 되기를 바랍니다.
추가 연습 문제
아래의 문제를 풀어보세요:
- 주어진 그래프에서 특정 노드 간의 최단 경로를 구하는 문제
- 미로 탐색 문제를 BFS를 이용하여 해결하기