[JAVA 03] 1697. 숨바꼭질

1697. 숨바꼭질 (S1)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	259328	76710	48775	26.011%

 

 

문제

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

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

입력

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

출력

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

---

summary

수빈이가 동생을 찾을 수 있는 가장 빠른 시간 구하기 

 

- 이동 방법1. 걷기는 X 에서 X-1 또는 X+1 로 이동

- 이동 방법2. 순간이동은 1초 후에 2*X 위치로 이동

- 수빈이는 처음 주어지는 범위 이외에 위치에도 이동이 가능

 

strategy

메모이제이션과  BFS 사용

 

- 수빈이가 몇 초 후에 해당 위치에 도착하는지 기록 (location[])

- 각 위치는 처음 한번만 방문 (location[])

- 수빈이의 이동 위치가 동생위치보다 먼 경우에는 X-1 만 사용 (if 조건)

- 수빈이 위치가 음수일 때는 더 좋은 경우의 수가 될 수 없으므로 고려하지 않음 (if 조건)

 

note

-  N(0 ≤ N ≤ 100,000), K(0 ≤ K ≤ 100,000)

 

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

public class Main {

    static int N, K;
    static int[] location;
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        /* input */
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        
        location = N > K ? new int[(N+1) * 2] : new int[(K+1) * 2];

        /* logic */
        BFS();

        /* output */
        System.out.println(location[K] - 1);
    }

    public static void BFS() {
        Queue<Integer> queue = new ArrayDeque<>();
        
        location[N] = 1; // 시작위치
        queue.add(N);
        
        while(!queue.isEmpty()){
            int current = queue.poll();

            int back = current - 1;
            int front = current + 1;
            int teleport = current * 2;

            if(current > 0 && location[back] == 0) { // 처음 방문, 양의 위치
                location[back] = location[current] + 1;
                queue.add(back); 
            }
            if(current < K && location[front] == 0) { // 처음 방문, K위치보다 크지 않음
                location[front] = location[current] + 1;
                queue.add(front); 
            }
            if(current < K && location[teleport] == 0) { // 처음 방문, K위치보다 크지 않음
                location[teleport] = location[current] + 1;
                queue.add(teleport); 
            }

            if(location[K] != 0) break;
        } 
    }
}

 

문제	결과	메모리	시간	언어코드	길이
1697	맞았습니다!!	17168	128	Java 11 / 수정	1646

 

MEMO

 -    이동 경우의 수를 배열로 관리하면 코드가 더 간결해질거같다. (move[] = new int[1, -1, 2])

            int mx = queue.poll();

            for(int m : move) {
                if(m == 2) mx *= 2;
                else mx += m;
            }

            if(mx < 0 || mx > 100000) continue;
            if(arr[mx] != 0) continue;

            location[mx] = location[current] + 1;
            queue.add(mx);

 

- 인덱스 범위 관리하는게 항상 어렵다. 언제쯤 안헷갈릴까 (이번에도 2번이나 런타임에러 뜸) 

// N 이 K보다 큰 경우 고려를 못함
location = new int[(N+1) * 2];