백준 13549(숨바꼭질3)

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

어떻게 하면 원하는 값까지 도달할 수 있을까. dfs는 한곳을 엄청 깊게 판다. 

 

그래서 원하는 값까지 도달하더라도 그 값이 최솟값이 아닐 가능성이 농후하다. 그래서 bfs

 

bfs에 단순 queue로 구성을 하려니 순간이동할때는 시간 소모가 안된다고 한다. 그래서 만약 단순 queue로 구성을 한다고 하면 경로는 더 길지만 시간이 적게 걸리는 경우를 확인하지 못한다. 

 

따라서 priority_queue로 시간이 작은 것부터 조사를 하면 괜찮지 않을까 생각한다. 

 

근데 여기서 만약에 조건을 추가하지 않고 단순하게 두배, +1, -1로 하게된다면 순간이동하는 경우에는 시간이 소모되지 않으므로 계속해서 순간이동하는 것부터 조사하게 될것이다. 

 

그렇다면 조건을 넣어주자 찾으려는 값이 40이고 현재의 값이 80이라면 현재의 값에 두배를 했을때 최단경로가 될 수 있을까? 찾으려는 값을 초과해서 두배를 한다면 최소 N번을 -해야하므로

 

걸리는 시간 >= 시간 + N 이 된다.

 

따라서 조건을 잘 넣어서 쓸데없는 연산을 하지 않도록 해준다. 

 

여기서 나는

			if (p.second * 2 < MAX - 1 && p.second  < K * 4)

 

이렇게 넣었다. 

 

그리고 주의해야 할 점이 하나 더 있다. 

 

만약에 100,000까지 가고싶다고 하자 

50,001에서 간다고하면 100,002까지 간 후에 -2하는것이 최단 경로일 것이다.

 

하지만 만약에 배열의 크기를 100,001까지로 제한해둔다면? 

 

원하는 결과를 찾을 수 없다. 따라서 배열의 크기를 잘 설정해야 한다. 

 

100,000 - N vs N*2 - 100,000 를 비교해서 대충 같아지는 N값의 두배이상을 설정해주면 되겠다.

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
#define MAX 200002

priority_queue<pair<int, int> > pq;
pair<int, int> p;
int N, K, num;
bool visited[MAX];

void solve() {
	pq.push(make_pair(0, N));
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		if (p.second == K) {
			cout << -p.first << "\n";
			return;
		}
		if (!visited[p.second]) {
			visited[p.second] = true;
			if(p.second < MAX-1)
				pq.push(make_pair((p.first - 1), p.second + 1));
			if (p.second > 0)
				pq.push(make_pair((p.first - 1), p.second - 1));
			if (p.second * 2 < MAX - 1 && p.second  < K * 4)
				pq.push(make_pair(p.first, p.second * 2));
		}

	}

}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K;
	solve();
}

 

 

다른 사람들 코드를 확인해보니깐, 그냥 queue로도 풀었다. 한번 코드 참조해서 공부 해봐야겠다.