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

 

 

 

 

BFS를 활용하면 풀수 있는 문제다.

관련 포스팅을 참고한 후 풀었다.

 

중요한 건 한번 방문한 곳은 다시 방문하지 않게 해야한다는 것.

pair를 사용해서 (위치, 시간) 쌍으로 queue에 넣었다. 

while문이 한바퀴를 돌 때 같은 초에 갈수 있는 같은 레벨의 위치들이 queue에 push되는데

queue에 일단 push 되면 같은 초(같은레벨) 인지 알 수 없기 때문이다. 

 

 

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

const int MAX = 1000000 + 1;

int N, K;
bool visited[MAX];

int minSecond(int N, int K) {
	queue<pair<int, int>> q;

	q.push(make_pair(N, 0));
	visited[N] = true;


	// 한번 돌때 같은'초'(트리에서 같은 레벨)에 갈수 있는 곳을 큐에 넣음.
	// 큐 안에선 같은 레벨인지 구분이 안되기 때문에 위치와 지점을 함께 저장하는 것이 필요.
	while (!q.empty()) {	
		int curLoc = q.front().first;
		int curSec = q.front().second;

		q.pop();

		// 도착했을 때
		if (curLoc == K) {
			return curSec;
		}

		// 한 칸 뒤로 갈 때
		if (0 <= curLoc - 1 && !visited[curLoc - 1]) {
			q.push(make_pair(curLoc - 1, curSec + 1));
			visited[curLoc - 1] = true;
		}

		// 한 칸 앞으로 갈 때
		if (curLoc + 1 < MAX && !visited[curLoc + 1]) {
			q.push(make_pair(curLoc + 1, curSec + 1));
			visited[curLoc + 1] = true;
		}

		// 두배로 앞으로 갈 때
		if (curLoc * 2 < MAX && !visited[curLoc * 2]) {
			q.push(make_pair(curLoc * 2, curSec + 1));
			visited[curLoc * 2] = true;
		}
	}
}

int main(void) {

	cin >> N >> K;

	cout << minSecond(N, K) << endl;

	return 0;
}