[백준] 13549번 : 숨바꼭질 3

문제

 

 

접근 방식

뒤로 이동은 x - 1, 앞으로 이동은 x + 1, 순간이동은 x * 2를 해주면서

동생의 좌표까지 가주면 되는 간단한 문제인데 함정이 몇 개 숨어있다.

 

뒤와 앞으로 이동하는 경우에는 이동시간이 1씩 증가하지만

순간이동의 경우에는 이동하는데 시간이 걸리지 않는다.

 

그래서 순간이동은 아무리 써도 시간이 걸리지 않기 때문에

순간이동을 우선적으로 사용해 주고 앞뒤로 이동해주어야 한다.

 

이동 순서가 바뀌게 되면 결과가 달라지는 문제라

이 부분을 신경 써줘야 한다.

 

BFS를 사용해서 풀 때 한 가지 더 조심해야 할 부분이 있는데

큐는 들어온 순서대로 실행되기 때문에 최단경로가

텔레포트를 3 연속으로 사용하는 경우라도

텔레포트 > 텔레포트 > 텔레포트 순서대로 실행되는 것이 아니라

(텔레포트 > 앞으로 이동 > 뒤로 이동) * 3 순서대로 실행된다.

 

그래서 텔레포트를 3번 하는 과정에서 앞이나 뒤로 이동하다

k에 도달하는 경우가 있을 수 있기 때문에

k에 도달했다고 종료하는 것이 아니라

큐가 빌 때까지 탐색을 계속해줘야 한다.

 

풀이

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());

		boolean[] isVisited = new boolean[100001];

		Queue<Subin> q = new LinkedList<>();
		q.offer(new Subin(n, 0));

		int min = Integer.MAX_VALUE;

		while (!q.isEmpty()) {
			Subin cur = q.poll();

			int x = cur.x;
			int move = cur.move;
			isVisited[x] = true;

			if (x == k) {
				min = Math.min(min, move);
				continue;
			}

			int back = x - 1;
			int front = x + 1;
			int tp = x + x;

			if (tp < 100001 && !isVisited[tp]) q.offer(new Subin(tp, move));
			if (front <= k && !isVisited[front]) q.offer(new Subin(front, move + 1));
			if (back >= 0 && !isVisited[back]) q.offer(new Subin(back, move + 1));
		}

		System.out.println(min);
	}

	private static class Subin {
		int x;
		int move;

		public Subin(int x, int move) {
			this.x = x;
			this.move = move;
		}
	}
}