[BAEKJOON] 13913 숨바꼭질 4

백준13913 숨바꼭질 4 풀이 정리

 

13913 숨바꼭질 4

문제 

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

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

 

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

 

입력

5 17

 

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

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

 

출력

4
5 4 8 16 17

풀이

1697 숨바꼭질 문제에  이동경로가 추가된 문제임

이동경로를 저장하기 위해 이전 위치 기억용 배열과 경로 기억용 벡터 추가

// 이전 위치 기억용 배열
int pre[100001] = { 0 };

// 이전 경로 기억용 벡터
vector<int> v;

queue에 이동 위치를 저장할때마다 이전 위치를 pre배열에 저장

		// 걷는경우(x - 1, x + 1), 순간이동 하는 경우( 2 * x) 
		for (int i = 0; i < 3; i++) {
			int nextposition = nowposition;
			switch (i) {
			case 0:
				nextposition = nowposition - 1;
				break;
			case 1:
				nextposition = nowposition + 1;
				break;
			case 2:
				nextposition = 2 * nowposition;
				break;
			}

			//범위, 방문 확인 후 큐에 push
			if ((nextposition >= 0) && (nextposition < 100001) && (visit[nextposition] == 0)) {
				q.push({ nextposition, nowsecond + 1 });
				visit[nextposition] = 1;
				// 이전 위치 저장
				pre[nextposition] = nowposition;
			}
		}

출발 위치부터 목표 위치에 도달할때까지 저장한 pre 배열의 이동 인덱스를 순회하며 이전 경로 기억 벡터에 위치 저장 후

역순 출력

	// 출발 위치 저장
	v.push_back(k);

	// 목표 위치에 도달할때까지 반복
	while(k != n) {
		// 이전 경로 기억 벡터에 이전 위치 저장
		v.push_back(pre[k]);
		k = pre[k];
	}

	for (int i = v.size() -1 ; i >= 0; i--) {
		cout << v[i] << " ";
	}

 

전체 코드

#include <iostream>
#include <queue>

using namespace std;

// 방문 확인용 배열
int visit[100001] = { 0 };

// 이전 위치 기억용 배열
int pre[100001] = { 0 };

// 너비 우선 탐색용 큐 (위치, 시간 저장)
queue<pair<int, int>> q;

// 이전 경로 기억용 벡터
vector<int> v;

// 수빈이의 위치, 동생의 위치
int n, k;

int bfs()
{
	// 출발 위치, 시간 push 후 방문 처리
	q.push(make_pair(n, 0));
	visit[n] = 1;

	while (!q.empty())
	{
		// 현재 노드 기억
		int nowposition = q.front().first;
		int nowsecond = q.front().second;
		q.pop();

		// 목표 위치 도달시 break
		if (k == nowposition) return nowsecond;

		// 걷는경우(x - 1, x + 1), 순간이동 하는 경우( 2 * x) 
		for (int i = 0; i < 3; i++) {
			int nextposition = nowposition;
			switch (i) {
			case 0:
				nextposition = nowposition - 1;
				break;
			case 1:
				nextposition = nowposition + 1;
				break;
			case 2:
				nextposition = 2 * nowposition;
				break;
			}

			//범위, 방문 확인 후 큐에 push
			if ((nextposition >= 0) && (nextposition < 100001) && (visit[nextposition] == 0)) {
				q.push({ nextposition, nowsecond + 1 });
				visit[nextposition] = 1;
				// 이전 위치 저장
				pre[nextposition] = nowposition;
			}
		}
	}
}

int main(void)
{
	int second = 0;

	cin >> n >> k;

	second = bfs();

	cout << second << endl;

	// 출발 위치 저장
	v.push_back(k);

	// 목표 위치에 도달할때까지 반복
	while(k != n) {
		// 이전 경로 기억 벡터에 이전 위치 저장
		v.push_back(pre[k]);
		k = pre[k];
	}

	for (int i = v.size() -1 ; i >= 0; i--) {
		cout << v[i] << " ";
	}

	return 0;
}