[C++]백준 1261번: 알고스팟

문제 출처

풀이

전형적인 BFS문제라고 생각했고 그렇게 접근했지만 알고리즘이 번뜩 떠오르지가 않았다. 그렇게 힌트를 보다 0-1BFS 알고리즘이라는 것을 접했고 이를 소개하고자 한다.

0-1 BFS
0-1BFS는 모든 간선의 가중치가 0 또는 1인 것을 뜻한다. 일반적인 다익스트라 알고리즘으로도 최소 거리를 찾을 수 있지만 0-1BFS는 조금 더 효율적인 방법을 제시한다. 알고리즘의 개요는 다음과 같다.

1. 가중치가 0인 간선을 따라 도달할 수 있는 모든 노드에 우선 접근한다.
2. 현재 따라 갈 수 있는 모든 간선 중 가중치가 0인 간선이 더 이상 존재하지 않다면 그제서야 가중치가 1인 간선을 따라간다.
3. 가중치가 1인 간선을 따라갈 때는 이전 비용보다 +1을 해준다.
4. 이 모든 과정을 deque를 통해 구현한다.

4번에 대해 구체적으로 살펴보자.
deque는 양방향 배열이라 생각하면 된다. 일반적인 vector와 다르게 앞으로도 push가 가능하다. 꺼낼 때에는 vector처럼 생각하면 된다.
왜 deque를 사용하냐면 우리는 가중치가 0인 간선과 가중치가 1인 간선으로 도달한 노드에 다른 우선순위를 매기고 싶기 때문이다. 왜냐하면 우리는 가중치가 0인 간선으로 도달한 노드부터 꺼내어 개요 1에 따라계속 가중치가 0인 간선을 먼저 찾을 것이기 때문이다.
이렇게 하면 된다. 가중치가 0인 간선을 만나면 push_front로 deque의 앞에 넣고 가중치가 1인 간선을 만나면 push_back으로 뒤에 넣는다. 그리고 deque에서 꺼낼 때에는 무조건 앞에서 부터 꺼낸다. 이렇게하면 무조건 가중치가 0인 간선을 따라 도달한 노드부터 탐색을 시작하고 그게 더이상 남지 않았다면 자연스레 가중치가 1인 간선을 따라 도달한 노드를 탐색하게 된다. 개요2가 자연스레 적용된다.
다음은 전체 코드이다.

#include<iostream>
#include<vector>
#include<deque>
using namespace std;

typedef pair<int, int> ii;
typedef pair<ii, int> iii;

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

int main() {
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	int M, N;
	cin >> M>> N;
	vector<vector<char>> place(N, vector<char>(M));
	vector<vector<bool>> visit(N, vector<bool>(M, 0));
	for ( int i = 0; i < N; i++ ) {
		for ( int j = 0; j < M; j++ ) {
			cin >> place[i][j];
		}
	}
	deque<iii> dq;
	dq.push_front(iii{ {0,0},0 });
	while ( !dq.empty() ) {
		int y = dq.front().first.first;
		int x = dq.front().first.second;
		int w = dq.front().second;
		dq.pop_front();
		if ( y == N - 1 && x == M - 1 ) {
			cout << w << endl;
			return 0;
		}

		for ( int i = 0; i < 4; i++ ) {
			int nextY = y + dy[i];
			int nextX = x + dx[i];
			if ( (nextY >= N || nextY < 0 || nextX >= M || nextX < 0) || visit[nextY][nextX] )continue;
			if ( place[nextY][nextX] == '0' ) {
				visit[nextY][nextX] = 1;
				dq.push_front(iii{ {nextY,nextX }, w});
			}
			else {//가중치가 1인 간선을 갔으므로 w+1을 해준다.
				visit[nextY][nextX] = 1;
				dq.push_back(iii{ {nextY,nextX }, w + 1 });
			}
		}


	}

	return 0;
}