백준 13549 숨바꼭질 3 c++ (다익스트라)

문제 출처 : https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라
• 0-1 너비 우선 탐색

풀이

순간 이동에도 1초가 든다고 하면 단순 최단 거리를 구하는 bfs라고도 할 수 있지만,

순간 이동에는 0초가 들고, x+1, x-1의 움직임에는 -1초가 든다.

즉 가중치가 다르기 때문에 다익스트라 문제라고 하는 것이 좀 더 맞는 것 같다.

 

수빈이가 동생을 찾기위한 움직임은 x*2 ,x+1, x-1 세 곳으로 움직일 수 있다.

x*2의 가중치는 0임에 주의하고, 수빈이가 동생을 만나면 바로 종료되기 때문에,

x*2 동작을 제일 먼저 수행하자.

구현 방법은 dp를 INF로 초기화하고, dp[next]가 dp[cur]+가중치보다 클 때만 탐색하는 방식과,

bool visited[MAX], int dp[MAX]를 따로 두고, visited[next]==false(방문하지 않음)이거나, dp[next]가 dp[cur]+가중치보다 클 때 탐색하는 방식으로 구현할 수 있다. 

두 방식의 차이는 dp를 INF로 초기화하느냐, 아니면 배열을 두 개를 이용하느냐 차이다.

 

2022.06.29 수정

			if (next >= 0 && next < MAX &&dp[next] > dp[cur] + time) {
				q.push(next);
				dp[next] = dp[cur] + time;
			}

아래 코드에선 bfs종료 조건(목적지에 도달했는지)을 next가 아닌 cur에서 검사한다.

따라서 cur==end 시점에선 이미 dp[end]의 가중치가 더 작은 값으로 초기화 되어있기 때문에 굳이 *연산을 먼저 할 필요가 없다.

N이 1이고 K가 2라고 하면

+1, -1, * 순으로 진행했을 때,

cur==end 조건문에선 dp[2]는 최종적으로 0 값이 들어가 있다.

만약 탐색 종료 조건을 next==end로 했으면 +1을 하는 순간 바로 종료 되므로 이땐 *연산을 먼저 수행하자.

코드1

#include <iostream>
#include <algorithm>
#include <queue>

#define MAX 100001
using namespace std;
int mov[3] = { 2,1,-1 };
int dp[MAX];

void bfs(int start, int end) {
	queue<int> q;
	q.push(start);
	dp[start] = 0;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (cur == end) {
			cout << dp[end];
			break;
		}
		//큐는 선입선출이기 때문에 순간이동을 제일 먼저 해야 한다.
		for (int i = 0; i < 3; i++) {
			int next,time;
			if (i == 0) {
				next = cur * 2;
				time = 0;
			}
			else {
				next = cur + mov[i];
				time = 1;
			}
			if (next >= 0 && next < MAX &&dp[next] > dp[cur] + time) {
				q.push(next);
				dp[next] = dp[cur] + time;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	fill_n(dp, MAX, 987654321);
	bfs(n, k);
	return 0;
}

코드2

#include <iostream>
#include <vector>
#include <queue>

#define MAX 100001
using namespace std;
int mov[3] = { 2,1,-1 };
bool visited[MAX];
int dp[MAX];


void bfs(int start, int end) {
	queue<int> q;
	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (cur == end) {
			cout << dp[end];
			break;
		}
		for (int i = 0; i < 3; i++) {
			int next,time;
			if (i == 0) {
				next = cur * 2;
				time = 0;
			}
			else {
				next = cur + mov[i];
				time = 1;
			}
			if (next >= 0 && next < MAX && (!visited[next] || dp[next] > dp[cur] + time)) {
				q.push(next);
				visited[next] = true;
				dp[next] = dp[cur] + time;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	
	bfs(n, k);
	return 0;
}