[JAVA] 백준 (골드5) 13549번 숨바꼭질 3

링크

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

---

문제 설명

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

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

---

입력 예제

5 17

---

출력 예제

2 (수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.)

---

정답 코드

목표 지점까지 최소 이동 횟수를 구해야 하므로 BFS를 이용한다.
단, 케이스마다 가중치가 다르기 때문에 우선순위 큐를 사용한다.
순간이동했을 때와 나머지 경우가 다르기 때문에
순간이동했을 때는 time을 그대로 큐에 삽입한다.
그리고 시간에 따라 오름차순으로 정렬하여
순간이동을 먼저 수행해준다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    private static final int N_SIZE = 100001;
    static boolean[] visit = new boolean[N_SIZE]; //방문 체크 배열

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        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());

        bfs(N, K);
    }

    //너비 우선 탐색 메서드
    static void bfs(int N, int K) {
    	//int 배열을 가지는 우선순위 큐 생성
        //배열의 1번째 원소를 기준으로 오름차순
        PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> x[1] - y[1]);

        queue.add(new int[]{N, 0});
        visit[N] = true;
        int nextPos = 0;

        //큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
        
            int[] cur = queue.poll();
            //현재 위치
            int curPos = cur[0];
            //현재 위치까지 걸린 시간
            int time = cur[1];
            //방문 처리
            visit[curPos] = true;
			//목적지에 도착했을 경우
            if (curPos == K) {
                System.out.println(time);
                break;
            }

            //3가지 경우의 수에 따라 반복
            for (int i = 0; i < 3; i++) {

                //2 * X로 이동
                if (i == 0) {
                    nextPos = curPos * 2;
                }
                //X + 1로 이동
                if (i == 1) {
                    nextPos = curPos + 1;
                }
                //X - 1로 이동
                if (i == 2) {
                    nextPos = curPos - 1;
                }
                //배열을 벗어날 경우
                if (nextPos < 0 || nextPos >= N_SIZE) {
                    continue;
                }
                //방문하지 않은 경우
                if (!visit[nextPos]) {
                    if (i == 0) {
                        queue.add(new int[]{nextPos, time});
                    } else {
                        queue.add(new int[]{nextPos, time + 1});
                    }
                }

            }

        }
    }
}

---

정리

숨바꼭질의 시리즈 문제이다. 대신 순간이동했을 때의 시간을 0초로 가중치가 달라졌다. 그래서 순간이동했을 때를 우선으로 고려해야 한다. 아무래도 그래프에 대해 잘 알지 못하다보니 우선순위 큐를 사용한다는 생각을 하지 못했고 큐로만 구현하다가 시간을 엄청 소비했다.