[코딩 테스트 준비 - 기초] 10. BFS - 최단 거리, 최소 비용

1. BFS만으로 풀 수 있는 문제

DFS와 BFS의 목적은 임의의 정점에서 시작해서 모든 정점을 한 번씩 방문하는 것으로 동일하다. 따라서 모든 인접 정점을 방문하는 목적이라면 DFS와 BFS 중 아무거나 사용해도 상관없다. 하지만, BFS만을 사용해야 하는 문제들이 있다. 바로 모든 가중치가 1일 때, 최단 거리를 구하는 문제이다!

 

cf. 가중치가 1이 아닌 경우 최단 거리를 구하는 문제는 Dijkstra로 푼다.

 

BFS를 이용해 해결할 수 있는 문제는 아래 조건을 만족해야 한다.

• 최단 거리, 최소 비용 문제이어야 한다.
• 간선의 가중치가 1이어야 한다.
• 정점과 간선의 개수가 문제의 조건에 맞춰 해결할 수 있어야 한다. (O(V + E)내에 해결 가능해야 함)
• 간선의 가중치가 최소 비용의 의미와 일치해야 한다. (최단 거리를 구하는 문제라면 가중치가 거리를 의미해야 함)

 

2. 문제

1) 가중치가 동일한 경우

[백준 1697 숨바꼭질]

• 문제: 수빈이가 동생을 찾는 가장 빠른 시간 구하기
• 간선의 가중치: 1초
• 시간복잡도: O(10만 + 30만) = 최대 40만
• 주의사항 - 문제의 입력은 10만까지이지만, 이동 가능한 곳은 최대 20만까지임을 확인할 수 있다!

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 200001; //이동가능한 범위는 20만!!
int dist[MAX];

int main(){
	int n, k;
	cin>>n>>k;

	queue<int> q;
	q.push(n);
	dist[n] = 1;

	while(!q.empty()){
		int x = q.front();
		q.pop();

		//이동 가능한 위치
		if(x - 1 >= 0 && !dist[x-1]){
			q.push(x-1);
			dist[x-1] = dist[x] + 1;
		}
		if(x + 1 < MAX && !dist[x+1]){
			q.push(x+1);
			dist[x+1] = dist[x] + 1;
		}
		if(2 * x < MAX && !dist[2*x]){
			q.push(2*x);
			dist[2*x] = dist[x] + 1;
		}
	}

	cout<<dist[k] - 1<<'\n';

	return 0;
}

 

[백준 13913 숨바꼭질4]

• 위 문제에 역추적이 추가된 것

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

const int MAX = 200001; //이동가능한 범위는 20만!!
int dist[MAX];
int route[MAX]; //이동 경로

int main(){
	int n, k;
	cin>>n>>k;

	queue<int> q;
	q.push(n);
	dist[n] = 1;

	while(!q.empty()){
		int x = q.front();
		q.pop();

		//이동 가능한 위치
		if(x - 1 >= 0 && !dist[x-1]){
			q.push(x-1);
			dist[x-1] = dist[x] + 1;
			route[x-1] = x;
		}
		if(x + 1 < MAX && !dist[x+1]){
			q.push(x+1);
			dist[x+1] = dist[x] + 1;
			route[x+1] = x;
		}
		if(2 * x < MAX && !dist[2*x]){
			q.push(2*x);
			dist[2*x] = dist[x] + 1;
			route[2*x] = x;
		}
	}

	int cnt = dist[k] - 1;
	cout<<cnt<<'\n';

	stack<int> s;
	s.push(k);
	while(cnt--){
		int x = s.top();
		s.push(route[x]);
	}

	while(!s.empty()){
		cout<<s.top()<<" ";
		s.pop();
	}

	return 0;
}

 

참고) 스택에 값을 넣을 때 for문 사용하기

두 개의 코드는 동일한 기능을 한다!

stack<int> s;
s.push(k);
while(cnt--){
    int x = s.top();
    s.push(route[x]);
}

stack<int> s;
for(int i=k; i!=n; i=route[i]){
	s.push(i);
}
s.push(n);

 

[백준 14226 이모티콘]

• 인접 정점으로 이동할 때 조건이 있는 경우 정점을 다른 것으로 보고 분리해서 생각해야 한다.
• 클립보드에 있는 이모티콘의 개수에 따라 1번 연산인 복사하기의 결과가 다르다.
• 즉, 화면에 있는 이모티콘 개수와 클립보드에 있는 이모티콘의 개수에 따라 정점을 나누어 처리해야 한다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 1001; //이론상 가능한 범위는 2001
int dist[MAX][MAX];

int main(){
	int n;
	cin>>n;
	memset(dist, -1, sizeof(dist));

	queue<pair<int, int>> q; //(s, c): 화면, 클립보드
	q.push(make_pair(1, 0));
	dist[1][0] = 0;

	while(!q.empty()){
		int s = q.front().first;
		int c = q.front().second;
		q.pop();

		if(dist[s][s] == -1){ //1번 연산: 클립보드 저장
			q.push(make_pair(s, s));
			dist[s][s] = dist[s][c] + 1;
		}
		if(s + c <= n && dist[s+c][c] == -1){ //2번 연산: 붙여넣기
			q.push(make_pair(s+c, c));
			dist[s+c][c] = dist[s][c] + 1;
		}
		if(s - 1 >= 0 && dist[s-1][c] == -1){ //3번 연산: 하나 삭제하기
			q.push(make_pair(s-1, c));
			dist[s-1][c] = dist[s][c] + 1;
		}
	}

	int ans = MAX;
	for(int i=0; i<=n; i++){
		if(dist[n][i] != -1)
			ans = min(ans, dist[n][i]);
	}
	cout<<ans<<'\n';

	return 0;
}

 

2) 가중치가 0과 1인 경우

위에서 BFS를 사용하기 위해서는 모든 가중치가 1로 동일해야 한다고 했다. 하지만 예외적으로 가중치가 0과 1인 문제를 BFS로 풀 수 있는 두 가지 방법이 있다.

• 두 개의 queue 사용하기 (코드는 이걸로)
• deque 사용하기

 

[백준 13549 숨바꼭질 3]

• 1697번의 숨바꼭질 문제와 달리,2*x의 순서를 가장 앞에 놓아야 정답 처리를 받는다. 이유는 아래 링크를 참고하자.
• https://www.acmicpc.net/board/view/38887#comment-69010

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 200001;
int dist[MAX];

int main(){
	int n, k;
	cin>>n>>k;

	queue<int> q; //현재 큐
	queue<int> nq; //다음 큐
	q.push(n);
	dist[n] = 1;

	while(!q.empty()){
		int x = q.front();
		q.pop();

		if(2 * x < MAX && !dist[2*x]){ //2*x가 가장 앞에 와야 한다.
			q.push(2*x);
			dist[2*x] = dist[x];
		}
		if(x - 1 >= 0 && !dist[x-1]){
			nq.push(x-1);
			dist[x-1] = dist[x] + 1;
		}
		if(x + 1 < MAX && !dist[x+1]){
			nq.push(x+1);
			dist[x+1] = dist[x] + 1;
		}

		if(q.empty()){
			q = nq;
			nq = queue<int>();
		}
	}

	cout<<dist[k] - 1<<'\n';

	return 0;
}

 

[백준 1261 알고스팟]

• 위 코드에서도 그랬지만, 방문하지 않는 경우를 if(!dist[nx][ny])로 작성하고 싶어서 dist[i][j]를 0으로 두었다.

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 101;
int a[MAX][MAX];
int dist[MAX][MAX];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int main(){
	int m, n;
	cin>>m>>n;

	char c;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin>>c;
			a[i][j] = c - 48;
		}
	}

	queue<pair<int, int>> q;
	queue<pair<int, int>> nq;
	q.push(make_pair(0, 0));
	dist[0][0] = 1;

	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for(int i=0; i<4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;

			if(!dist[nx][ny]){
				if(a[nx][ny]){ //벽
					nq.push(make_pair(nx, ny));
					dist[nx][ny] = dist[x][y] + 1;
				} else{ //빈방
					q.push(make_pair(nx, ny));
					dist[nx][ny] = dist[x][y];
				}
			}
		}
		if(q.empty()){
			q = nq;
			nq = queue<pair<int, int>>();
		}
	}

	cout<<dist[n-1][m-1] - 1<<'\n';

	return 0;
}