[백준] 13549-숨바꼭질 3(C++)

문제링크:www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

대부분

• 순간 이동(0초 소요)은 걷는 이동(1초 소요)보다 더 빠르기때문에, 우선 순위가 높다. 

라는 조건을 생각해서 deque나 우선순위 큐를 사용해서 구현하셨더군요!

저는 일반 큐를 사용해서 구현했습니다. (수가 100,000까지 이기때문에 모든 방문노드를 들러도 된다고 인지했습니다. )

 

 

아래는 정답코드입니다.

천천히 확인해보세요.

#include <iostream>
#include <queue>
using namespace std;
int n = 0, k = 0;
int visited[100001] = { 0, };


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	queue <int> que;


	cin >> n >> k;
	que.push(n);
	visited[n] = 1;

	while (!que.empty()) {
		
		int v = que.front();
		que.pop();
		//cout << v << endl;
		for (int j = v; j <= 100000; j *= 2) { // 0초 후에 2*X의 위치로 이동
			if (j == 0) break;
			if (visited[j] == 0) {
				visited[j] = visited[v];
				que.push(j);
			}
		}
		if (visited[v + 1] == 0 && (v+1) <= 100000) {
			visited[v + 1] = visited[v] + 1;
			que.push(v + 1);
		}
		if (visited[v - 1] == 0 && (v-1) >= 0) {
			visited[v - 1] = visited[v] + 1;
			que.push(v - 1);
		}



	}

	cout << visited[k] - 1 << endl;
	return 0;
}