[백준] 1697번: 숨바꼭질

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

어떻게 생각하고 문제를 풀었는가?

현재 위치가 X일때 목표지점 K로 이동할 수 있는 방법은 X-1, X+1, X*2로 3가지이지만 만약 X가 K보다 큰 값을 가지고 있을 경우 X+1, X*2는 최단시간을 구하는 데 큰 도움이 되지 않습니다.

BFS를 수행하고, 같은 위치에 반복 도달을 검사에서 제외함으로써 문제를 해결할 수 있다고 생각하였습니다.

코드

package com.boj;
import java.io.*;
import java.util.*;

class Main {
    static int N, K;
    static boolean[] visited;
    static Queue<Subin> queue;
    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());
        queue = new LinkedList<>();
        if(K<N){
            System.out.println(N-K);
            return;
        }
        visited = new boolean[K*2+1];
        visited[N] = true;
        queue.offer(new Subin(0,N));
        while(!queue.isEmpty()){
            Subin cur = queue.poll();
            if(cur.pos==K){
                System.out.println(cur.count);
                break;
            }
            else{
                if(cur.pos>0 && !visited[cur.pos-1]){
                    visited[cur.pos-1] = true;
                    queue.offer(new Subin(cur.count+1, cur.pos-1));
                }
                if(cur.pos<K){
                    if(!visited[cur.pos+1]){
                        visited[cur.pos+1] = true;
                        queue.offer(new Subin(cur.count+1, cur.pos+1));
                    }
                    if(!visited[cur.pos*2]){
                        visited[cur.pos*2] = true;
                        queue.offer(new Subin(cur.count+1, cur.pos*2));
                    }
                }
            }
        }
        br.close();
    }
    static class Subin{
        int count;
        int pos;
        Subin(int count, int pos){
            this.count = count;
            this.pos = pos;
        }
    }
}

ㅂQueue로 BFS를 구현한 코드입니다.

현재 위치와 이동 횟수를 저장하기 위해 클래스를 정의하였으며, 위치에 따라 X-1, X+1, X*2의 이동을 수행하여 먼저 N위치에 도달한 이동 횟수를 결과로 출력합니다.

K보다 큰 값을 갖는 위치에서 +1, *2의 이동은 최소 이동을 구하는데 아무런 도움이 되지 않기 때문에 현재 위치가 K보다 작은 값을 가질 때에만 +1, *2의 이동을 수행할 수 있도록 하였으며 방문 체크 배열도 K*2+1까지만 선언하였습니다.

만약 N값이 K보다 크다면 -1의 이동만 반복하는 것이 최소 이동이므로 BFS를 수행하지 않고 N-K의 값으로 결과를 출력합니다.