백준 13549 자바 - 숨바꼭질 3 문제

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

앞선 숨바꼭질 문제와 차이점은 순간이동시 0초가 걸린다는 점이다. 이 때문에 앞서 풀었던 동일 시간에 3가지 방향을 처리하는 방법으로 해결하기 어려워졌다.

그래서 위치와 시간을 가지는 객체를 하나 만들고 처리하게 만들었다.

 

주의점이라면 3가지 방향으로가능 경우에서 순간이동을 하는 경우를 가장 먼저 계산해야한다는 것이다.

순간이동의 경우 시간이 들지않기 때문에 방문처리를 할 경우 가장 먼저 되어야하기 때문이다. 만약 다른 경우가 먼저 계산되서 방문처리가 되고 순간이동 로직이 도는 경우 큐에 추가 되지않게 되어 실제 그 위치에 방문할수있는 시간보다 높은 값이 저장되게 되기때문이다.

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

// 숨바꼭질3 문제 - 13549번
class Human {
    int x;
    int time;

    public Human(int x, int time) {
        this.x = x;
        this.time = time;
    }
}

public class HideAndSeek3 {

    static int N, K;
    static int time = Integer.MAX_VALUE;
    static boolean[] visited = new boolean[100001];

    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());

        if(N == K){
            System.out.println(0);
        }else {
            bfs(N);
            System.out.println(time);
        }
    }

    static void bfs(int start) {
        Queue<Human> q = new LinkedList<>();
        q.offer(new Human(start, 0));
        visited[start] = true;

        while (!q.isEmpty()) {
            Human now = q.poll();

            if(now.x == K) {
                time = Math.min(time, now.time);
            }

            int next;
            // 다음에서 영역을 방문 처리
            // *2의 경우 time 이 증가하지 않으므로 다른 이동보다 먼저 계산되어야함.
            next = now.x * 2;
            if(next < 100001 && !visited[next]) {
                visited[next] = true;
                q.offer(new Human(next, now.time));
            }

            next = now.x - 1;
            if(next >= 0 && !visited[next]) {
                visited[next] = true;
                q.offer(new Human(next, now.time + 1));
            }

            next = now.x + 1;
            if(next < 100001 && !visited[next]) {
                visited[next] = true;
                q.offer(new Human(next, now.time + 1));
            }
        }
    }
}