0-1 BFS

그래프 변의 가중치가 모두 0 아니면 1인 그래프에서는 BFS와 다익스트라를 합친 듯한 느낌의 알고리즘인 0-1 BFS를 써서 최단 경로를 구할 수 있습니다. 알고리즘은 간단합니다. 꼭짓점의 집합을 $V$, 출발점을 $s$, 각 꼭짓점까지 최단 거리를 저장하는 배열을 $dist$라 할 때 의사코드는 아래와 같습니다.

\[ \begin{align}
& \textbf{for } \text{each vertex } v \in V \\
& \qquad dist[v] \leftarrow \infty \\
& dist[s] \leftarrow 0 \\
& \\
& Q \leftarrow \emptyset \\
& \text{PushBack}(Q, s) \\
& \textbf{while } Q \neq \emptyset \\
& \qquad u \leftarrow \text{PopFront}(Q) \\
& \qquad \textbf{for } \text{each edge } e \text{ adjacent to } u \\
& \qquad\qquad v \leftarrow \text{the opponent vertex of } u \text{ in } e \\
& \qquad\qquad w \leftarrow \text{the weight of } e \\
& \qquad\qquad \textbf{if } dist[v] > dist[u] + w \\
& \qquad\qquad\qquad dist[v] \leftarrow dist[u] + w \\
& \qquad\qquad\qquad \textbf{if } w = 0 \\
& \qquad\qquad\qquad\qquad \text{PushFront}(Q, v) \\
& \qquad\qquad\qquad \textbf{else} \\
& \qquad\qquad\qquad\qquad \text{PushBack}(Q, v)
\end{align} \]

$Q$의 앞쪽과 뒤쪽 모두에 원소를 넣을 수 있어야 하기 때문에 큐를 쓰는 BFS와 달리 $Q$가 덱(deque)이어야 합니다.

응용

BOJ 2636:: 치즈

icpc.me/2636

예전에 풀이를 올렸던 문제입니다. 그땐 다익스트라로 풀었고요, 지금은 0-1 BFS로 풀어봅시다. 먼저 모든 칸을 그래프의 꼭짓점으로 두고, 인접한 칸 사이에 변을 놓습니다. 변의 가중치는 치즈가 있는 칸으로 가면 1, 없는 칸으로 가면 0입니다.

이때 제일 왼쪽 위에서 출발하여 치즈가 있는 어떤 칸까지 최단 거리를 구하면 그것이 그 칸이 녹는 데 걸리는 시간입니다. 정답은 최단 거리의 최댓값과 그 값을 갖는 치즈의 개수가 되겠죠.

BOJ 6087:: 레이저 통신

icpc.me/6087

저택 문제와 거의 똑같습니다. 모든 칸을 “가로”와 “세로” 두 꼭짓점으로 나눠서 가로 꼭짓점은 가로로 이웃한 다른 가로 꼭짓점과 가중치 0인 변으로 이어주고, 세로 꼭짓점은 세로로 이웃한 세로 꼭짓점과 가중치 0으로 이어주고, 같은 칸의 두 꼭짓점끼리는 가중치 1인 변으로 이어서 최단 거리를 구하면 정답입니다.