[Java] BOJ13913, 백준 - 숨바꼭질 4

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

13913번: 숨바꼭질 4

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512MB	17519	6112	4252	37.728%

문제

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

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

 

입력

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

 

출력

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

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

 

** 숨바꼭질1, 2, 3, 4 문제가 있기 때문에 차례로 푸는 것을 추천

 

<풀이>

수빈이가 동생을 찾는 가장 빠른 시간을 구해야 한다.

이동하는 시간(=가중치)가 0과 1뿐이고, 최단 거리를 구하는 알고리즘이기 때문에 BFS를 이용하면 구할 수 있다.

 

*최소 시간 구하기

가중치가 둘 다 1일 경우에는 일반적인 BFS를 이용해 큐 하나만 사용해서 풀 수 있지만, 두 가중치가 0/1로 다르기 때문에 큐를 두 개 이용해준다.

• 순간이동을 하는 경우: 시간의 소모값이 없기 때문에 현재 큐에 그대로 넣어준다.
• 앞뒤로 한 칸 이동하는 경우: 시간이 1초 걸리기때문에 1초 후의 큐에 넣어준다.

원하는 지점에 이동할 때까지 과정을 반복해주면 K지점까지 이동하는 시간의 최솟값을 구할 수 있다.

 

*이동 경로 구하기

K지점으로 이동하기까지 어떠한 경로로 이동하는지 구하기 위해서 이전의 경로를 저장해줄 배열을 만든다.

예를 들어서 수빈이가 5에서 17로 이동하기 위해서 5-10-9-18-17 순서로 이동했다면,

arr[10] = 5;

arr[9] = 10;

arr[18] = 9;

이런 식으로 현재의 지점으로 오기 직전에 어디 있었는지 저장해준다.

K 지점에 도착했을 때 이를 되돌아가며 경로를 찾아주면 전체 이동 경로를 구할 수 있다.

 

+추가사항

문제를 봤을 때, 앞으로 이동하는 방법은 1칸 이동하는 방법과 두 배 이동하는 방법으로 총 두가지가 있지만,

뒤로 이동하는 방법은 1초를 소요하여 한 칸 가는 방법 뿐이다.

따라서 N>K일 경우, 수빈이가 동생이 있는 지점까지 이동하는 방법은 N-1부터 K까지 한 칸씩 뒤로 이동하는 방법 한 가지 뿐이다. 그래서 이 경우에는 BFS를 이용하지 않고 그냥 출력해주었다.

 

소스코드

import java.io.*;
import java.util.*;

public class Main {

	private static int[] arr;
	private static Queue<Integer> queue;
	private static int k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		// N >= K인 경우 출력하고 바로 종료
		if (n >= k) {
			System.out.println(n - k);
			for (int i = n; i >= k; i--) {
				System.out.print(i + " ");
			}
			System.exit(0);
		}

		queue = new LinkedList<Integer>();
		arr = new int[100002];
		for (int i = 0; i < arr.length; i++)
			arr[i] = -1;
		arr[n] = 0;

		// BFS를 이용하여 최소 시간 구하기
		queue.add(n);
		while (!queue.isEmpty()) {
			int x = queue.poll();
			// 뒤로 이동
			move(x, x - 1);
			// 앞으로 이동
			move(x, x + 1);
			// 순간이동
			move(x, 2 * x);
		}

		String s = "";

		int cnt = 0;
        // 이동 경로 구하기
		while (k != n) {
			cnt++;
			s = k + " " + s;
			k = arr[k];
		}
		System.out.println(cnt);
		System.out.println(n + " " + s);

	}

	private static void move(int x, int nx) {
		if (nx >= 0 && nx < arr.length && arr[nx] == -1) {
			arr[nx] = x;
			queue.add(nx);

			if (nx == k) {
				return;
			}
		}
	}
}