0-1 BFS

가중치가 없는, 또는 모든 간선의 가중치가 1인 그래프를 생각하자. 그러한 그래프에서 한 점으로부터의 최단거리는 BFS로 구할 수 있다. 이것을 응용해서 간선의 가중치가 0 또는 1인 그래프에서 거리를 구해보자. (가중치가 0 또는 x인 경우에도 풀 수 있다.)

가중치 0의 간선으로 이어진 정점들은 모두 거리가 같다. 따라서 가중치 0의 간선을 만나면 연결된 정점들을 모두 같은 거리로 설정해주면 된다. BFS에 이를 적용하기 위해서는 queue가 아니라 deque를 이용하면 된다. 가중치 0의 간선은 먼저 처리해야 하므로 deque의 앞에 넣으면 된다. 

https://codeforces.com/blog/entry/22276 참고.

 

0-1 BFS를 이용하면 아래 문제들을 풀 수 있다.

https://www.spoj.com/problems/KATHTHI/

https://community.topcoder.com/stat?c=problem_statement&pm=10337

https://codeforces.com/gym/100625 의 J

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2620

https://codeforces.com/contest/173/problem/B

https://a2oj.com/p?ID=28

 

내 코드

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define fi first
#define se second

const int MAXN = 1010;
const int INF = 1 << 30;

int N, S;				// 정점의 개수, 시작점
vector<pii> ed[MAXN];			// 간선(가중치, 연결된 정점)
int dis[MAXN];				// S로부터의 거리

void bfs() {
	deque<int> dq;
	for(int i = 1; i <= N; i++) dis[i] = INF;
	dq.push_back(S);
	dis[S] = 0;
	while(!dq.empty()) {
		int t = dq.front();
		dq.pop_front();
		for(auto a : ed[t]) {
			if(dis[t] + a.fi < dis[a.se]) {
				dis[a.se] = dis[t] + a.fi;
				if(a.fi == 0) dq.push_front(a.se);	// deque의 앞에 삽입
				else dq.push_back(a.se);		// deque의 뒤에 삽입
			}
		}
	}
}