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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 사용하여 풀이했다.

1) 수빈이의 현재 위치 n과 동생의 위치 k를 입력 받아 저장한다.
=> 이 때 n은 시작점, k는 목표 지점, 각 위치 지점들을 노드로 볼 수 있다.

2) 시작점에서 각 위치까지 최단 거리를 저장하는 배열 dp를 선언하고, dp의 모든 값을 무한대로 초기화한다.

3) 다익스트라 알고리즘을 실행하여 시작점에서부터 각 위치까지의 최단 거리를 구한다.

• 최소힙으로 구현하기 위해 우선순위 큐 pq를 선언하고, 오름차순으로 정렬되도록 한다.
  • pq에는 노드 정보 (해당 노드까지 최소 거리, 노드 번호)가 저장된다.
• pq에 (0, 시작 위치)를 삽입한다.
• dp[start](시작점에서부터 시작점까지의 최단 거리)를 0으로 초기화한다.
• pq가 빌 때까지 아래 과정을 반복한다.
  • pq에 저장되어 있는 노드 중 가중치가 가장 작은 노드에 대한 정보를 꺼낸다.
    • dist : 현재 노드까지의 거리
    • cur : 현재 노드의 번호
  • 만약 dp[cur] < dist라면 이미 최단 거리가 구해진 노드이므로 무시한다.
  • 위 경우가 아니라면 아래 과정을 반복한다.
    • 해당 문제는 미리 간선 정보가 제공되어 저장하고 시작하는 것이 아니고,
      현재 위치에서 1, 1, 0의 가중치로 -1, +1, *2 위치에 이동이 가능하도록 되어있다. 즉, 이동했을 때의 위치가 현재 위치의 인접 노드라고 보는 것이다.
    • 따라서 cost에 현재 노드까지의 거리 + 현재 노드 ~ 이동했을 때 거리를 저장한다.
    • 만약 이동 했을 때 수빈이가 있을 수 있는 범위(0 이상 100000 이하)에 위치하고, cost가 저장되어있던 이동 위치의 dp보다 작다면 (cost < dp[인접 노드])
      • 인접 노드의 dp를 cost로 갱신한다.
      • 갱신된 인접 노드 정보 (인접 노드까지의 최소 거리, 노드 번호)를 pq에 삽입한다.

4) 위 과정이 끝나면 dp에는 시작점부터 다른 노드까지의 최소 거리들이 저장된다.
이 때, 동생의 위치 k까지의 최단 거리를 알고 싶은 것이기 때문에 dp[k]를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
typedef pair<int, int> pii;

int n, k;
int dp[100001];
const long long INF = 1e9;

pii move(int cur, int i)
{
	if (i == 0)
		return pii(cur - 1, 1);
	else if (i == 1)
		return pii(cur + 1, 1);
	else
		return pii(cur * 2, 0);
}

void dijkstra(int start)
{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push(pii(0, start));
	dp[start] = 0;

	while (!pq.empty())
	{
		int dist = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (dp[cur] < dist) continue;
		for (int i = 0; i < 3; i++)
		{
			pii curEdge = move(cur, i);
			int cost = dist + curEdge.second;
			if (curEdge.first >= 0 && curEdge.first <= 100000 && cost < dp[curEdge.first])
			{
				dp[curEdge.first] = cost;
				pq.push(pii(cost, curEdge.first));
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> k;
	fill(dp, dp + 100001, INF);
	dijkstra(n);
	cout << dp[k];
}