백준 / 13549번 / 숨바꼭질 3

[문제]

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

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

[입력]

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

[출력]

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

[예제 입력]

5 17

[예제 출력]

2

[힌트]

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

 

---

 

숨바꼭질 문제 (https://www.acmicpc.net/problem/1697) 에서 순간이동 시간만 달라진 문제인데,

생각보다 어렵고 까다로웠던 문제다.

기존 숨바꼭질 문제와 달라진 점은 순간 이동이 1초에서 0초로 바뀌었다는 점이다.

 

그래서, 나머지는 기존과 같은 방법으로 코드를 작성하고

순간이동의 경우엔 arr값을 변경해주지 않았는데 계속 20% 즈음에서 실패가 떴다.

 

알고보니, 순간이동과 걷기 처리 순서 때문이었다.

예를 들어서 4->6 으로 간다고 했을 때, 순간이동을 먼저 하지 않으면 2초가 걸리지만

순간이동을 먼저 하면 1초가 걸린다는 문제가 있었다. 

따라서, 순간이동을 먼저 처리해주지 않으면 이미 방문 표시가 되기 때문에 최소의 시간을 구할 수 없게 되는 것이다.

 

마찬가지로, 걷는 경우에 x-1 혹은 x+1로 이동하는데 이 부분 또한 x-1을 먼저 처리해줘야 했다.

이 부분을 생각하지 못했어서 좀 복잡했던 문제이다. 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N; // 수빈 위치
    static int K; // 동생 위치

    static int[] arr = new int[100001]; // 위치 배열
    static boolean[] check = new boolean[100001]; // 방문 여부

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        System.out.println(bfs());
    }

    private static int bfs() {
        Queue<Integer> queue = new LinkedList<>();

        check[N] = true;
        queue.add(N);

        while (!queue.isEmpty()) {
            int q = queue.poll();

            if (q == K) {
                break;
            }

            if (q * 2 >= 0 && q * 2 < 100001 && !check[q * 2]) { // 순간이동
                queue.add(q * 2);
                check[q * 2] = true;
                arr[q * 2] = arr[q];
            }
            
            if (q - 1 >= 0 && q - 1 < 100001 && !check[q - 1]) { // 걷기 (x-1)
                queue.add(q - 1);
                check[q - 1] = true;
                arr[q - 1] = arr[q] + 1;
            }
            
            if (q + 1 >= 0 && q + 1 < 100001 && !check[q + 1]) { // 걷기 (x+1)
                queue.add(q + 1);
                check[q + 1] = true;
                arr[q + 1] = arr[q] + 1;
            }
        }
        return arr[K];
    }
}

 

---

 

 

이런식으로 처리하는 방법 말고 다른 방법이 없나 찾아봤는데

특정 위치를 방문한 적이 있더라도, 순간이동으로 이동할 경우 더 빠르게 방문을 할 수 있기 때문에, 

방문 여부 배열을 boolean이 아니라 int형으로 선언하고, 몇 초에 도달했는지를 저장해주는 방법이 있었다.

 

해당 코드는 아래 주소에서 확인할 수 있다.

https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-13549-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-3-JAVA%EC%9E%90%EB%B0%94

[백준] 13549 : 숨바꼭질 3 (JAVA/자바)