BOJ 13549 숨바꼭질 3

처음 떠오른 방법은 queue에다가 각 인접 노드를 {노드,가중치 합} 로 저장하고 큐를 순회하면서 해당 노드의 가중치 합을 최소로 만들어 주는 것이였다. 즉 BFS 방식을 떠올린 것이다. 하지만 이 문제를 BFS로 풀려면 큐에서 가중치가 0인 노드부터 방문해야 하는 조건이 붙는다. 

 

위에 조건을 적용하지 않아 제출하면 자꾸 8%에서 틀렸다고 나왔다.....

 

BFS로 해결되지 않아 다익스트라를 적용하였다. 다익스트라가 적용될 수 있는 이유는 "가중치가 모두 0 또는 양수이고, 특정 지점 a에서 b 지점까지의 최단 경로 가중치"를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다.

 

하지만 기존 다익스트라와 조금 다른점은 인접노드에 대한 정의가 나와있지 않기 때문에 각 지점에서 인접한 노드를 X+1, X-1, X*2  이렇게 3개로 표현하고 각각의 가중치는 시간으로 1,1,0이라는 것을 유추하여 인접노드를 정의 해야한다.

 

//다익스트라
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;

bool visited[100001];


void dijk(int start,int end)
{
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,start });
	visited[start] = true;

	while(!pq.empty())
	{
		int time = pq.top().first;
		int next = pq.top().second; 
		pq.pop();

		if(next == end)
		{
			cout << time;
		}

		if(next > 100000 || next < 0)
		{
			continue;
		}

		if(next * 2 <= 100000 && !visited[next * 2])
		{
			visited[next * 2] = true;
			pq.push({ time, next * 2 });
		}

		if(next + 1 <= 100000 && !visited[next + 1])
		{
			visited[next + 1] = true;
			pq.push({ time + 1, next + 1 });
		}
		if(next - 1 >= 0 && !visited[next - 1])
		{
			visited[next - 1] = true;
			pq.push({ time + 1, next - 1 });
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	memset(visited, false, sizeof(visited));

	int n, k;

	cin >> n >> k;

	dijk(n,k);
}

//BFS
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

queue<pair<int, int>> q;
vector<int> time;
bool visited[100001];


void bfs(int start,int end)
{
	q.push({ start,0 });

	while(!q.empty())
	{
		int next = q.front().first; 
		int weight = q.front().second;
		q.pop();

		if(next > 100000 || next < 0)
		{
			continue;
		}

		if(visited[next] == false)
		{
			time[next] = min(time[next], weight);
			visited[next] = true;

			if(next < 1)
			{
                q.push({ next * 2, weight + 0 });
				q.push({ next + 1, weight + 1 });
			}
			else
			{
                q.push({ next * 2, weight + 0 });
				q.push({ next - 1, weight + 1 });
				q.push({ next + 1, weight + 1 });
			}
		}
		else
		{
			time[next] = min(time[next], weight);
		}

	}

	cout << time[end];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	memset(visited, false, sizeof(visited));

	int n, k;

	cin >> n >> k;

	for(int i = 0; i < 100001; i++)
	{
		time.push_back({ 111111});//{time}
	}
	time[n] = { 0 };

	bfs(n,k);
}