백준 - 13549 숨바꼭질3

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

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는 정수이다.

 

출력

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

---

풀이 방법

이전 숨바꼭질2 에서 더더 발전한 문제! 무려 순간이동하면 시간이 흐르지 않는다(초사이언도 아니고)

이번에는 무려 *2 연산 시 가중치가 없다 => *2 하면 0초 이다.

이전과는 가장 큰 차이점은 바로 여기에 있다. 이전 문제까지가 +1, -1, *2 모두 가중치가 +1초 였다면 이번에는 +1, -1 만 +1초 이고 *2 에는 가중치가 +0초 이다.

 

이 문제는 이러한 특성 때문에 아래와 같이 2가지로 생각해야한다.

1. 숨바꼭질2 처럼 이미 방문한 좌표에도 재방문이 가능하다는 것을 생각해야한다. 이때 이미 방문했던 next 좌표의 시간보다 현재 좌표의 시간+연산에 따른 시간이 더 작은 경우에만 방문해야한다. 이후 재방문한 좌표에는 새로운 방문 시간 - 더 작은 시간 - 을 넣어주어야한다.

2. 이전 문제들과는 다르게 최솟값을 찾았다고 해서 바로 return 하면 안된다. bfs 를 끝까지 돌리면서 더 작은 값이 있는지 확인해야한다. 이는 1) 에서 이야기한 재방문에 따라서 arr 에 담기는 시간이 달라질 수 있기 때문이다.

 

1) 과 2) 와 관련해서는 쉽게 생각해서 n = 4, k =9 가 들어오는 경우를 생각해보자
n 이 9까지 가려면 8을 반드시 거쳐야한다. 때문에 4->8 까지 가는 경우의 수를 생각한다. 경우의 수는
 크게 3가지 정도이다.
- 4->3->6->7->8 : 총 3초 
- 4->5->6->7->8 : 총 4초
- 4->8 : 총 1초// 결국 arr[8] 의 최솟값은 0 이 된다.
결과적으로 8->9 까지 최소값은 1초가 된다. 4->8(0초)->9(1초) => 1초
즉 arr[8] 에는 총 3번이나 방문 할 수 있지만 결국 *2 연산의 값인 0 초가 담길 때 result 가 가장 작은 최솟값이 된다. 

 

더 자세한 것은 코드의 주석 참고!!

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Quiz_13549 {
    static int n, k;
    static int[] arr = new int[100001]; // 방문 시간 저장 배열
    static int result = Integer.MAX_VALUE; // 최솟값 체크 변수
    static Queue<Integer> q = new LinkedList<>();

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

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

        // 배열 전체를 -1 로 초기화
        // -1 로 초기화하는 이유는 n*2 했을 때 이전 문제와는 다르게 가중치가 +1 이 아닌 0 이기 때문
        // 따라서 0 초가 존재하기 때문에 이를 계산하기 위해서 -1로 초기화
        Arrays.fill(arr, -1);

        if (n >= k) {
            System.out.println(n - k);
        }else{
            q.offer(n);
            arr[n] = 0;
            System.out.println(findBrother3());
        }
    }

    static int findBrother3(){
        while (!q.isEmpty()) {
            int num = q.poll();

            // 만약 현재 q에서 빼왔던 arr[num] 의 값이 현재 result 보다 크다면 더 이상 계산할 필요도 없이
            // continue;
            if (result < arr[num]) {
                continue;
            }

            // move 배열은 이동값과 이동 시간(초)를 설정한 2차원 배열
            // num-1, num+1 은 1초, num*2 는 0 초가 걸린다
            int[][] move = {
                    {num-1, 1},
                    {num+1, 1},
                    {num*2, 0}
            };

            // move 배열에서 값을 얻어오기 위한 for문 실행
            for(int i=0; i<3; i++){
                int next = move[i][0]; // 이러면 next 값은 num+1, num-1, num*2 중 하나가 된다

                if (next == k) { // next 값이 k 와 일치하면
//                    return arr[num]+move[i][1];
                    // 이전에 방문했었던 arr[num] 에 num+1, num-1, num*2 에 맞는 가중치를 더한다.
                    // 즉 num+1, num-1 은 arr[num]+1 이 될 것이고, num*2 의 경우에는 arr[num]+0 이 될 것이다.
                    // 이후 result 와 최솟값을 비교해서 저장
                    result = Math.min(result, arr[num]+move[i][1]);

                    // next 값이 k 와 일치하지 않고, next >= 0, next <= 100000 이 만족하는 상황이라면
                    // 총 2가지 경우에 대해서 생각한다.
                    // 첫째로 arr[next] 에 방문하지 않은 경우 => arr[next] = -1 인 경우에는 방문후 queue 에 next 를 넣고, arr[next] 의 방문시간을 표시한다
                    // 다음으로 arr[next] 에 이미 방문한 경우 => arr[next] != -1 인 경우에는
                    // arr[next] 가 arr[num]+move[i][1] 보다 큰 수 인지 여부를 확인하고,
                    // 만약 arr[next] 보다 arr[num]+move[i][1] 이 작은 경우 해당 next 좌표에 재방문 후 arr[next] 값을 수정한다.

                    // 이는 4->9 가 주어졌을 때 9 이전 좌표인 8 이라는 좌표에 도착하기 위한 경우를 생각하면 된다.
                    // 4->3->6->7->8 : 총 3초 =
                    // 4->5->6->7->8 : 총 4초
                    // 4->8 : 총 0초
                    // 결국 arr[8] 의 최솟값은 0 이 되고, 8->9 까지는 1 초 임으로
                    // 답은 1초가 된다.
                }else if (next >= 0 && next <= 100000 && (arr[next] == -1 || arr[next] > arr[num]+move[i][1]) )  {
                    q.offer(next);
                    arr[next] = arr[num] + move[i][1];
                }

            }
        }

        return result;
    }
}