백준 13913번 숨바꼭질 4

- 문제 설명

 

수빈이는 현재 점 N 에 있고, 동생은 점 K 에 있다.

 

수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

 

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

 

 

- 입력

 

1) 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다.  (0 ≤ N ≤ 100,000), (0 ≤ K ≤ 100,000)

 

 

- 출력

 

1) 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

2) 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

 

 

* 문제 풀이의 핵심

 

 

1. BFS

 

이 문제는 수빈이가 현재 위치에서 주변으로 이동하는데 경우의 수가 3가지 있으며 가중치가 1인 그래프로 생각할 수 있습니다.

 

경우의 수는 현재 위치가 X일 때 X-1 로 이동, X+1로 이동, 2*X로 이동 3가지 경우로 나뉘어 있으며, 모든 행동이 1초 시간 걸리기 때문에 가중치가 1 이라고 볼 수 있습니다.

 

수빈이가 현재위치에서 동생이 있는 위치로 가는 모든 경로를 구해서 가장 짧은 값을 택하면 정답을 찾을 수 있습니다.

 

 

2. 알고리즘

 

<1> 범위는 100,000 이지만 LEN 는 200,000 으로 설정한 이유

 

수빈이와 동생이 있을 수 있는 위치는 100,000 이 최대 이지만 움직일 수 있는 범위를 최대 위치의 2배로 설정한 이유는 다음과 같습니다.

 

수빈이가 최대 움직일 수 있는 범위를 넘어서서 움직인 다음 X-1 연산을 통해 동생을 찾는 것이 더 빠를 수 있기 때문입니다.

 

ex) 예시

4 15

경우 1 : 4 8 16 15 (0 ≤ N, K ≤ 30)

경우 2 : 4 8 9 10 11 12 13 14 15 (0 ≤ N, K ≤ 15)

 

 

<2> 동생을 찾는 과정

 

while문을 사용해 BFS 를 탐색할 때 3가지 경우가 생기기 때문에 해당 위치를 방문하지 않았다면 큐에 값을 넣어준다.

 

배열은 visited (방문여부), from (경로 저장), dist (거리 저장) 3가지가 필요하다.

 

다음에 방문하는 경로는 무조건 현재 거리 + 1 값을 가지기 때문에 dist[K] 값을 찾으면 정답을 찾을 수 있다.

 

 

int next1 = cur + 1;

if (next1 < LEN) {
  if (!visited[next1]) {
    q.push(next1);
    from[next1] = cur;
    dist[next1] = dist[cur] + 1;
    visited[next1] = true;
  }
}

 

 

<3> 경로를 출력하는 과정

 

- from[a] = b : a의 값은 b로부터 생성되었음을 저장하는 배열

 

재귀적으로 from 배열을 탐색하다가 N과 from 배열의 값이 같아지면 출력을 하면 된다. (자동으로 역순으로 출력됨)

 

 

void find_path(int N, int K) {
	if (N != K) {
		find_path(N, from[K]);
	}
	cout << K << " ";
}

 

 

- 소스코드

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<queue>
#include<tuple>

using namespace std;

const int LEN = 200000;

bool visited[LEN + 1];
int from[LEN + 1];
int dist[LEN + 1];

int bfs(int N, int K) {
	int ret = 0;

	queue<int> q;
	q.push(N);
	visited[N] = true;
	dist[N] = 0;
	
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		int next1 = cur + 1;
		int next2 = cur - 1;
		int next3 = cur * 2;

		if (next1 < LEN) {
			if (!visited[next1]) {
				q.push(next1);
				from[next1] = cur;
				dist[next1] = dist[cur] + 1;
				visited[next1] = true;
			}
		}

		if (next2 >= 0) {
			if (!visited[next2]) {
				q.push(next2);
				from[next2] = cur;
				dist[next2] = dist[cur] + 1;
				visited[next2] = true;
			}
		}

		if (next3 < LEN) {
			if (!visited[next3]) {
				q.push(next3);
				from[next3] = cur;
				dist[next3] = dist[cur] + 1;
				visited[next3] = true;
			}
		}
	}

	return dist[K];
}

void find_path(int N, int K) {
	if (N != K) {
		find_path(N, from[K]);
	}
	cout << K << " ";
}

int main() {
	int N, K;
	cin >> N >> K;

	cout << bfs(N, K) << "\n";
	find_path(N, K);
	cout << "\n";
}

 

 

 

- 문제링크 : www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

 

- 제출한 코드

 

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요