[JAVA 09] 13549. 숨바꼭질3

 

13549. 숨바꼭질3 (G5)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	115700	29893	19925	24.034  %

 

 

 

문제

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

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

입력

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

출력

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

 

 

---

summary

수빈이가 동색을 찾을 수 있는 가장 빠른 시간은 몇 초 후인가

 

- 걸을 때, 1초  X-1 또는 X+1

- 순간이동, 0초  2*X

 

strategy

BFS 와 메모이제이션 (숨바꼭질1 과 유사하다.)

 

note

- N(0 ≤ N ≤ 100,000)

-  K(0 ≤ K ≤ 100,000)

 

 

정답 코드

 

import java.util.*;
import java.io.*;

public class Main {

    static int MAX = 100000;
    static int N, K;
    static int DP[];
    
    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());

        DP = new int[MAX + 1];
        
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(N);
        DP[N] = 1;

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

            if(K == current) break;

            if(current * 2 <= MAX && DP[current * 2] == 0) {
                DP[current * 2] = DP[current]; 
                queue.add(current * 2);
            }

            if(current - 1 >= 0 && DP[current - 1] == 0) { // 걷기
                DP[current - 1] = DP[current] + 1; 
                queue.add(current - 1); // x - 1; 
            }

            if(current + 1 <= MAX && DP[current + 1] == 0) { // 걷기
                DP[current + 1] = DP[current] + 1; 
                queue.add(current + 1); // x + 1;
            }
        }

        System.out.println(DP[K] - 1);
    }
}

 

틀린 코드

import java.io.*;
import java.util.*;

public class Main {

    static int MAX = 100005; 
    static int N, K;
    static int[] DP;
    
    public static void main(String[] agrs) 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());

        DP = new int[2*MAX];

        /* logic */
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(N); // 시작위치치
        DP[N] = 1;
        
        while(!queue.isEmpty()) {
            int current = queue.poll();
            
            if(current < K) { // 수빈이가 동생보다 큰 수에 있는지 체크
                int i = 1;

                while(true) { // 순간이동
                    int next = (int) (current * Math.pow(2, i++)); // 2배수
                    
                    if(next > 2 * K) break; // 불필요한 연산 제거
                    if(DP[next] != 0) break; // 방문 여부 체크 
                
                    queue.add(next); 
                    DP[next] = DP[current];
                } 
            }
            
            if(DP[current + 1] == 0) { // 걷기
                DP[current + 1] = DP[current] + 1; queue.add(current + 1); // x + 1;
            }

            if(current > 0 && DP[current - 1] == 0) { // 걷기ㄱ
                DP[current - 1] = DP[current] + 1; queue.add(current - 1); // x - 1; 
            }
            
            if(DP[K] != 0) break;
        }
        
        System.out.println(DP[K] -1);
    }
}

 

문제	결과	메모리	시간	언어코드	길이
13549	맞았습니다!!	16096 KB	120 ms	Java 11 / 수정	1290

 

MEMO

- 문제 이해를 잘못했다. 순간이동은 0초 걸린다고 해서 2를 곱해서 갈 수 있는 모든 장소를 살폈는데 아니었다.

 

- 코드가 왜 틀렸는지 모르겠는데  걷기할 때 x + 1 먼저 체크하고  x - 1 방문하면 통과못한다. 

  > 가중치 문제라고 한다. https://www.acmicpc.net/board/view/38887#comment-69010