[C++] 백준 13549번: 숨바꼭질 3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

그냥 단순한 bfs 문제인줄 알았지만 간선이 0인 경우를 고려해야 해서 까다로운 문제였다..

 

결국 해결 하지 못해 힌트를 보고 말아서 좀 아쉬운 문제였다..

 

참고: www.acmicpc.net/board/view/38887#comment-69010

글 읽기 - [13549-숨바꼭질3] BFS 큐에 넣는 순서 질문

위에서 나오듯이 

1. 다익스트라 알고리즘을 사용하는 법

 

2. 0-1 BFS: 간선이 0(순간이동)을 넣을 떄 큐의 맨 앞에 넣는 법

 

3. * 2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

 

위의 세가지 방법 중에 하나를 사용하는 되는 문제였고 난 덱을 사용해서 결국 2번 방법을 사용해 풀 수 있었다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

deque<pair<int, int>> dq;
int visit[100001];
int n, k;

void bfs(int x) {
	visit[x] = 1;
	dq.push_back({ x, 0 });
	while (!dq.empty()) {
		int y = dq.front().first;
		int z = dq.front().second;
		dq.pop_front();
		if (y == k) {
			cout << z;
			return;
		}
		if (2 * y <= 100000 && visit[2 * y] == 0) {
			visit[2 * y] = 1;
			dq.push_front({ 2 * y , z});
		}
		if (y - 1 >= 0 && visit[y - 1] == 0) {
			visit[y - 1] = 1;
			dq.push_back({ y - 1, z+1 });
		}
		if (y + 1 <= 100000 && visit[y + 1] == 0) {
			visit[y + 1] = 1;
			dq.push_back({ y + 1, z+1 });
		}
	}
}

int main() {
	cin >> n >> k;
	bfs(n);
	return 0;
}