[백준] 숨바꼭질4

문제

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다.
만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

풀이

문제를 간략히 하면, 일직선상에 있는 점 A와 점 B가 있다. 점 A는 현재 위치에서+1 칸, -1칸, x2칸 이동할 수 있다. 매 초가 지날때 마다 점 A의 현재 좌표와 지금까지 이동 경로를 묶음으로 큐에 저장하여 BFS로 풀었다. 지금까지의 이동 경로는 리스트가 아닌 String으로 하였다.

근데 이렇게 코드를 짜서 submit을 했더니, run time error가 나길래 백준 질문게시판을 보니 점 A가 10만 에 위치해있고, 점 B가 0에 위치해있으면 O(N^2) 풀이법이 이 10만 * 10만 이 됨으로 시간초과가 났다. 따라서 예외처리를 하나 해주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
//큐에 담을 한 쌍 
class Pair {
	int x;
	String y;

	Pair(int a, String b) {
		x = a;
		y = b;
	}

	@Override
	public String toString() {
		return this.y;
	}

	public boolean isequal(int b) {
		return x == b;
	}
}

public class Main {

	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());
		int K = Integer.parseInt(st.nextToken());

		Queue<Pair> q = new LinkedList<>();
		if (N == K) {
			System.out.println(0);
			System.out.println(N);
		}else if (N > K){
			int time  = N - K ;
			StringBuilder sb = new StringBuilder("");
			for(int i =  N ; i >= K ;i--) {
				sb.append(i).append(" ");
			}
			System.out.println(time);
			System.out.println(sb.toString());
		}
		else {
			boolean visit[] = new boolean[1000001];

			String answer = "";
			/* 시작 점 삽입. */
			q.offer(new Pair(N, Integer.toString(N)));
			boolean findanswer = false;
			int time = -1;
			while (!findanswer) {
				time++; //시간 증가.
				int size = q.size();
				for (int i = 0; i < size; i++) {
					//System.out.println("현재i"+i);
					Pair temp = q.poll(); //큐에서 하나 꺼낸다. 
					if (visit[temp.x]) 
						continue;
					visit[temp.x] = true;
					int num = temp.x;
					String str = temp.y;

					if (temp.isequal(K)) {
						findanswer = true;
						answer = temp.toString();
						break;
					} else {
						if(num-1 >0) //왼쪽으로 이동
						q.offer(new Pair(num - 1,str +" " + Integer.toString(num - 1)));
						if(num+1 < 100001)//오른쪽으로 이동
						q.offer(new Pair(num +1,str +" "+ Integer.toString(num + 1)));
						if(num * 2 < 100001)//두배 이동
						q.offer(new Pair(num *2,str +" "+  Integer.toString(num *2)));
					}
				}
			}
			System.out.println(time);
			System.out.println(answer);
		}

	}
}