[알고리즘 Deep Dive #5] BFS 완전 정복: 숨바꼭질 시리즈로 배우는 BFS의 모든 것
알고리즘 Deep Dive #5 – BFS: 숨바꼭질 1~5번 풀이를 통해 기본 BFS부터 0-1 BFS, 레벨 탐색, 홀짝 BFS까지
BFS 기본 원리
BFS(Breadth-First Search, 너비 우선 탐색)는 그래프에서 가장 먼저 도달하는 경로가 곧 최단 경로가 되는 상황에서 사용하는 탐색 알고리즘이다.
특히 모든 간선의 가중치가 동일한 그래프에서는 BFS가 매우 강력하다. 시작 노드에서 가까운 노드부터 레벨(level) 단위로 확장되기 때문에, 어떤 노드를 처음 방문했을 때의 거리가 곧 최단 거리가 된다.
이 특징 덕분에 BFS는 다음과 같은 문제에서 자주 사용된다.
- 최소 이동 횟수 문제
- 격자(grid) 최단 경로
- 상태 공간 탐색 (예: 숨바꼭질, 퍼즐, 게임)
- 시간 단위 시뮬레이션
BFS의 핵심 아이디어
- Queue(큐) 를 사용하여 탐색 순서를 관리한다.
- 시작 노드를 큐에 넣는다.
- 큐에서 하나씩 꺼내면서 인접 노드를 탐색한다.
- 아직 방문하지 않은 노드를 큐에 넣고 거리를 갱신한다.
이 과정은 자연스럽게 다음과 같은 구조가 된다.
1
2
3
4
5
Start
├─ level 1
│ ├─ level 2
│ │ ├─ level 3
즉, 거리 0 → 거리 1 → 거리 2 → … 순서로 확장된다.
BFS 기본 구현 (Python)
다음은 가장 기본적인 BFS 구조이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque
def bfs(start, end, graph):
visited = {start: 0}
q = deque([start])
while q:
node = q.popleft()
if node == end:
return visited[end]
for next_node in graph[node]:
if next_node not in visited:
visited[next_node] = visited[node] + 1
q.append(next_node)
여기서 중요한 포인트는 두 가지다.
- visited[node] = 거리
- 큐에 들어가는 순간 방문 처리
이 방식 덕분에 같은 노드를 여러 번 방문하는 것을 방지하면서 동시에 최단 거리 계산이 가능하다.
BFS 시간 복잡도
그래프의 정점 수를 V, 간선 수를 E라고 하면
1
시간 복잡도: O(V + E)
각 노드와 간선을 최대 한 번씩만 탐색하기 때문에 매우 효율적이다.
한 줄 정리
가중치가 동일한 그래프에서 최단 경로 문제 → BFS
이제 이 기본 개념을 바탕으로 백준 숨바꼭질 시리즈를 통해 BFS가 어떻게 확장되는지 하나씩 살펴보자.
숨바꼭질 1: 기본 BFS
수빈이 위치 N, 동생 위치 K
이동 방법:x-1,x+1,2x
모든 이동 시간은 1초
이 문제는 BFS의 가장 기본적인 형태를 그대로 사용하는 문제다.
이동 비용이 전부 동일하기 때문에 그래프 최단 경로 문제 → BFS로 바로 연결된다.
핵심은 단순하다.
- 현재 위치에서 이동 가능한 다음 위치 탐색
- 아직 방문하지 않았다면 큐에 추가
- 이전 위치의 시간 +1로 거리 갱신
처음으로 K에 도달했을 때의 시간이 곧 최단 시간이 된다.
상태 공간 해석
이 문제를 그래프로 보면 다음과 같다.
1
2
3
정점(vertex) : 현재 위치 x
간선(edge) : x → x-1, x+1, 2x
비용(cost) : 1
즉, 0 ~ 100000 범위의 정점 그래프에서 최단 거리를 구하는 문제다.
구현 아이디어
두 가지 배열만 있으면 된다.
1
2
visited[x] = 시작점에서 x까지 걸린 시간
queue = BFS 탐색 순서
처음 방문할 때만 큐에 넣기 때문에
같은 위치를 여러 번 탐색하지 않는다.
Python 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
MAX = 100001
visited = [-1] * MAX
visited[N] = 0
q = deque([N])
while q:
x = q.popleft()
if x == K:
print(visited[K])
break
for nx in [x-1, x+1, 2*x]:
if 0 <= nx < MAX and visited[nx] == -1:
visited[nx] = visited[x] + 1
q.append(nx)
핵심 포인트
- visited = 거리 배열
- 처음 방문할 때만 큐에 넣기
- 도착하면 바로 종료
1
visited[nx] = visited[x] + 1
이 한 줄이 BFS 최단 경로의 핵심이다.
한 줄 정리
이동 비용이 모두 동일한 최단 경로 문제 → BFS
숨바꼭질 2: 최단 경로의 개수 세기
수빈이 위치 N, 동생 위치 K
이동 방법:x-1,x+1,2x
출력: 최단 시간 + 그 시간으로 도달하는 방법의 수
숨바꼭질 1과 거의 동일한 문제지만 한 가지가 추가된다.
1
2
3
최단 시간
+
그 시간으로 도달하는 방법의 개수
즉, 단순히 최단 거리만 구하는 BFS가 아니라
최단 경로의 개수까지 세야 하는 BFS다.
핵심 아이디어
두 개의 배열을 사용한다.
1
2
dist[x] = 시작점에서 x까지의 최단 시간
count[x] = x까지 최단 시간으로 도달하는 방법의 수
초기 상태는 다음과 같다.
1
2
dist[N] = 0
count[N] = 1
BFS에서 발생하는 두 가지 경우
다음 위치 nx로 이동할 때 두 가지 상황이 생긴다.
1️⃣ 처음 방문하는 경우
아직 nx에 도달한 적이 없다면
1
2
dist[nx] = dist[x] + 1
count[nx] = count[x]
즉,
- 최단 거리 갱신
- 경로 수 그대로 전달
2️⃣ 같은 최단 거리로 다시 도달한 경우
이미 방문했지만 같은 최단 거리로 도달한 경우다.
1
dist[nx] == dist[x] + 1
이 경우는 새로운 최단 경로가 추가된 것이므로
1
count[nx] += count[x]
경로 수를 누적한다.
Python 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from collections import deque
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
MAX = 100001
dist = [-1] * MAX
count = [0] * MAX
dist[N] = 0
count[N] = 1
q = deque([N])
while q:
x = q.popleft()
for nx in [x-1, x+1, 2*x]:
if 0 <= nx < MAX:
# 처음 방문
if dist[nx] == -1:
dist[nx] = dist[x] + 1
count[nx] = count[x]
q.append(nx)
# 같은 최단 거리로 재방문
elif dist[nx] == dist[x] + 1:
count[nx] += count[x]
print(dist[K])
print(count[K])
왜 BFS에서 가능한가?
BFS는 거리 순서대로 탐색한다.
1
거리 0 → 거리 1 → 거리 2 → ...
따라서
1
dist[nx] == dist[x] + 1
이라는 조건이 “같은 최단 거리 경로”라는 것을 보장한다.
핵심 패턴
최단 경로 개수 문제는 거의 항상 이 패턴을 사용한다.
1
2
3
4
5
6
if dist[next] == -1:
dist[next] = dist[cur] + 1
count[next] = count[cur]
elif dist[next] == dist[cur] + 1:
count[next] += count[cur]
한 줄 정리
최단 거리 + 경로 개수 → BFS + count 배열
숨바꼭질 3: 0-1 BFS
수빈이 위치 N, 동생 위치 K
이동 방법:x-1,x+1,2x
이동 시간
걷기 x±1: 1초순간이동 2x: 0초
이 문제부터 BFS에 중요한 변화가 생긴다.
1
이동 비용이 모두 같지 않다
숨바꼭질 1에서는 모든 이동이 1초였지만,
이번 문제에서는 순간이동(2x) 이 0초다.
1
2
3
x → x-1 : 1초
x → x+1 : 1초
x → 2x : 0초
즉, 간선의 가중치가 두 종류다.
1
0 또는 1
이 경우 사용하는 알고리즘이 바로 0-1 BFS다.
왜 일반 BFS가 안 될까?
일반 BFS는 다음 가정을 가지고 있다.
1
모든 간선의 비용이 동일
하지만 이 문제는
1
2
0초 이동
1초 이동
이 섞여 있기 때문에 탐색 순서가 깨질 수 있다.
그래서 우선순위를 조정하는 BFS가 필요하다.
0-1 BFS 핵심 아이디어
deque를 이용해 비용에 따라 삽입 위치를 다르게 한다.
1
2
비용 0 → deque 앞에 삽입 (appendleft)
비용 1 → deque 뒤에 삽입 (append)
즉,
1
2
현재 시간과 동일한 이동 → 먼저 처리
시간이 증가하는 이동 → 나중에 처리
이렇게 하면 다익스트라 없이도 최단 거리를 구할 수 있다.
동작 원리
예를 들어 어떤 위치 x에서 다음 이동이 있다고 하자.
1
2
3
x → 2x (0초)
x → x+1 (1초)
x → x-1 (1초)
처리는 다음과 같이 이루어진다.
1
2
3
appendleft(2x)
append(x+1)
append(x-1)
그래서 0초 이동이 항상 먼저 탐색된다.
Python 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import deque
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
MAX = 100001
dist = [-1] * MAX
dist[N] = 0
q = deque([N])
while q:
x = q.popleft()
if x == K:
print(dist[K])
break
for nx in [2*x, x-1, x+1]:
if 0 <= nx < MAX and dist[nx] == -1:
if nx == 2*x: # 비용 0
dist[nx] = dist[x]
q.appendleft(nx)
else: # 비용 1
dist[nx] = dist[x] + 1
q.append(nx)
핵심 패턴
0-1 BFS의 핵심 코드는 이것이다.
1
2
3
4
if cost == 0:
q.appendleft(next)
else:
q.append(next)
그리고 거리 갱신은
1
dist[next] = dist[cur] + cost
언제 0-1 BFS를 사용할까?
다음 조건이면 거의 항상 0-1 BFS다.
1
2
3
간선 가중치가 0 또는 1
최단 경로 문제
그래프 크기가 큼
이 경우
1
2
다익스트라 → O(E log V)
0-1 BFS → O(V + E)
로 훨씬 빠르다.
한 줄 정리
가중치가 0 또는 1인 최단 경로 문제 → 0-1 BFS
숨바꼭질 4: 경로 출력
수빈이 위치 N, 동생 위치 K
이동 방법:x-1,x+1,2x
출력: 최단 시간 + 실제 이동 경로
지금까지는 최단 시간만 구했다.
하지만 이번 문제에서는 실제 이동 경로까지 출력해야 한다.
즉 결과가 다음과 같이 나온다.
1
2
4
5 10 9 18 17
이 문제의 핵심은 경로를 역추적하는 것이다.
핵심 아이디어: parent 배열
BFS로 탐색할 때 각 노드가 어디서 왔는지 기록하면 된다.
1
parent[x] = x로 오기 직전 위치
예를 들어 탐색이 다음과 같이 진행되었다고 하자.
1
5 → 10 → 9 → 18 → 17
이 경우 parent 배열은 다음처럼 저장된다.
1
2
3
4
parent[10] = 5
parent[9] = 10
parent[18] = 9
parent[17] = 18
경로 복원 방법
목표 위치 K부터 거꾸로 따라가면 된다.
1
2
3
4
cur = K
while cur != -1:
path.append(cur)
cur = parent[cur]
그러면 경로가 거꾸로 저장된다.
1
17 18 9 10 5
마지막에 뒤집으면 된다.
1
path.reverse()
Python 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import deque
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
MAX = 100001
dist = [-1] * MAX
parent = [-1] * MAX
dist[N] = 0
q = deque([N])
while q:
x = q.popleft()
if x == K:
break
for nx in [x-1, x+1, 2*x]:
if 0 <= nx < MAX and dist[nx] == -1:
dist[nx] = dist[x] + 1
parent[nx] = x
q.append(nx)
path = []
cur = K
while cur != -1:
path.append(cur)
cur = parent[cur]
path.reverse()
print(dist[K])
print(*path)
핵심 패턴
경로 출력 BFS는 항상 이 구조를 사용한다.
1
2
dist[next] = dist[cur] + 1
parent[next] = cur
그리고 마지막에
1
K → parent[K] → parent[parent[K]] → ...
순으로 역추적한다.
언제 이 패턴을 사용할까?
다음 조건이면 parent 배열 BFS다.
1
2
3
최단 경로 문제
+
실제 이동 경로 출력
이 패턴은 다음 문제들에서도 자주 등장한다.
1
2
3
4
그래프 최단 경로
미로 탐색
게임 상태 이동
퍼즐 문제
한 줄 정리
최단 거리 + 실제 경로 출력 → BFS + parent 배열
숨바꼭질 5: 레벨 BFS + 홀짝 BFS
수빈이 위치 N, 동생 위치 K
이동 방법:x-1,x+1,2x
동생은 매 초마다 이동 거리가 증가
이 문제는 숨바꼭질 시리즈 중 가장 난이도가 높은 문제다.
기존 BFS에 두 가지 개념이 추가된다.
1
2
1. 동생의 위치가 매 초마다 변한다
2. 같은 위치라도 시간의 홀짝에 따라 상태가 다르다
접근 방법
1. 동생의 위치 변화
동생은 매 초마다 이동 거리가 증가한다.
1
2
3
4
5
t = 0 : K
t = 1 : K + 1
t = 2 : K + 1 + 2
t = 3 : K + 1 + 2 + 3
...
즉 위치는 다음 수식으로 표현된다.
1
K + t*(t+1)//2 # 등차수열의 합
예를 들어
1
2
3
4
5
6
K = 5
t = 0 → 5
t = 1 → 6
t = 2 → 8
t = 3 → 11
따라서 BFS 탐색 중 현재 시간에 따라 동생 위치를 계산해야 한다.
2. 같은 위치를 다시 올 수 있다
예를 들어 어떤 위치 P에 도달했다고 하자.
1
... → P
그 이후 다음 이동을 반복하면
1
P → P+1 → P
즉 2초 후 다시 P에 올 수 있다.
따라서 이러한 와리가리 권법에 따라
1
2
P를 짝수 시간에 방문
→ 이후 짝수 시간에 계속 P 가능
1
2
P를 홀수 시간에 방문
→ 이후 홀수 시간에 계속 P 가능
3. 그래서 visited를 2차원으로 만든다
일반 BFS
1
visited[x]
하지만 이 문제는
1
visited[time_parity][x]
즉
1
2
visited[0][x] = 짝수 시간에 x 방문 가능 여부
visited[1][x] = 홀수 시간에 x 방문 가능 여부
4. 만나는 조건
시간 t에 동생 위치가 pos라고 하자.
1
pos = K + t*(t+1)//2
이때 다음 조건이 만족하면 만난다.
1
visited[t % 2][pos] == True
즉 같은 시간의 홀짝에서 같은 위치에 있어야 한다.
Python 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from collections import deque
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
MAX = 500001
visited = [[False] * MAX for _ in range(2)]
visited[0][N] = True
q = deque([(N, 0)])
while q:
pos, sec = q.popleft()
# 시간에 따라 동생의 위치를 업데이트해준다.
brother = K + sec * (sec + 1) // 2
if brother >= MAX:
print(-1)
break
# 수빈이가 t와 같은 홀짝으로 현재 동생 위치에 도달한 적 있으면
# 그 이후 제자리 반복으로 정확히 t초에 동생 위치에 있을 수 있음
if visited[sec % 2][brother_pos]:
print(sec)
break
for nxt in [pos-1, pos+1, pos*2]:
if 0 <= nxt < MAX and not visited[(sec+1) % 2][nxt]:
visited[(sec+1) % 2][nxt] = True
q.append((nxt, sec+1))
핵심 개념 정리
이 문제는 BFS에 다음 개념들이 결합된 문제다.
1
2
3
상태가 시간에 따라 변하는 BFS
+
같은 위치라도 시간 상태가 다른 BFS
즉
1
상태 = (위치, 시간의 홀짝)
한 줄 정리
시간에 따라 상태가 변하면 → BFS 상태에 시간을 포함해야 한다
전체 비교
숨바꼭질 시리즈는 BFS가 어떻게 확장되는지 단계적으로 보여주는 문제 묶음이다.
문제가 하나씩 진행되면서 BFS에 새로운 개념이 추가된다.
정리하면 다음과 같다.
1
2
3
4
5
숨바꼭질 1 → 기본 BFS
숨바꼭질 2 → BFS + 경로 개수
숨바꼭질 3 → 0-1 BFS
숨바꼭질 4 → BFS + 경로 복원
숨바꼭질 5 → 레벨 BFS + 홀짝 BFS
각 문제에서 추가되는 핵심 개념을 비교하면 다음과 같다.
| 문제 | 핵심 기법 | 추가 개념 |
|---|---|---|
| 숨바꼭질 1 | 기본 BFS | - |
| 숨바꼭질 2 | BFS + count | 같은 최단거리 재방문 처리 |
| 숨바꼭질 3 | 0-1 BFS | appendleft / append |
| 숨바꼭질 4 | BFS + parent | 경로 역추적 |
| 숨바꼭질 5 | 레벨 BFS + 홀짝 | visited[2], 시간 상태 |
난이도 증가 구조
이 시리즈는 다음과 같은 순서로 BFS를 확장한다.
1
2
3
4
5
기본 BFS
→ BFS + 상태 추가
→ BFS + 가중치 처리
→ BFS + 경로 복원
→ BFS + 시간 상태
즉 단순한 BFS가 점점 일반적인 그래프 탐색 문제로 확장되는 과정을 보여준다.
BFS 확장의 핵심 패턴
숨바꼭질 시리즈에서 등장한 BFS 확장 패턴을 정리하면 다음과 같다.
1
2
3
4
5
dist[] → 최단 거리
count[] → 최단 경로 개수
parent[] → 경로 복원
deque → 0-1 BFS
visited[2] → 시간 상태 관리
실제 알고리즘 문제에서 BFS는 이 패턴들을 조합해서 사용하는 경우가 많다.
한 줄 정리
BFS 문제는 대부분 “상태를 어떻게 확장할 것인가”의 문제다.
BFS 적용 판단 기준
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
최단 경로 문제인가?
└── 가중치가 모두 같은가?
└── Yes → 기본 BFS
└── 0과 1 두 종류인가?
└── Yes → 0-1 BFS (deque)
└── No → 다익스트라
경로를 출력해야 하는가?
└── Yes → parent 배열 추가
상태가 변하는가? (동생처럼 매 초 위치 변경)
└── Yes → 레벨 단위 BFS
도달 가능 여부가 홀짝에 따라 다른가?
└── Yes → visited[2] 홀짝 분리
Tags: #알고리즘 #BFS #그래프탐색 #너비우선탐색 #최단경로 #01BFS #그래프알고리즘 #백준 #코딩테스트 #Python #Algorithm