[C++]백준 - 13913번 문제

13913번: 숨바꼭질 4 (acmicpc.net)

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는 정수이다.

 

 

출력

---

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

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

 

 

---

 

생각해 볼 점

---

우선, BFS를 통해 경로를 찾을 수 있습니다.

 

경로를 찾을 때, 흔히 사용하는 Visited 배열이 이전경로를 담도록 합니다.

 

그러면, Visited를 되짚어가서 경로를 역추적 할 수 있습니다.

 

Visited 배열 초기값들 : -1 (미방문)

 

최단 경로 예시 : 1 -> 2 -> 4

 

Visited[4] = 2

Visited[2] = 1

Visited[1] = -1

 

 

 

코드

---

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

int main() 
{
	int N, K;
	scanf("%d %d", &N, &K);
	
	queue<int> q;
	
	q.push(N);
	int visited[100001];
	fill_n(visited, 100001, -1);
	
	int result = -1;
	
	//BFS 알고리즘
	while(!q.empty())
	{
	    vector<int> next_q;
	    while(!q.empty())
	    {
	        int current = q.front();
	        q.pop();
	        //종료 조건
	        if(current == K)
	        {
	            while(!q.empty()) q.pop();
	            next_q = vector<int>();
	            break;
	        }
	        
	        //다음 행선지
	        int next[3] = {current + 1, current -1, current * 2};
	        for(int i = 0; i < 3; i++)
	        {
	            if(0 <= next[i] && next[i] <= 100000 && visited[next[i]] == -1)
	            {
	                visited[next[i]] = current;
	                next_q.push_back(next[i]);
	            }
	        }
	        
	    }
	    for(int next : next_q) q.push(next);
	    result++;
	}
	printf("%d\n", result);
	
	
	//출력부
	int index = K;
	stack<int> st;
	while(index != N)
	{
	    st.push(index);
	    index = visited[index];
	}
	st.push(N);
	
	while(!st.empty())
	{
	    printf("%d ", st.top());
	    st.pop();
	}
	return 0;
}

 

그 외

---