[백준] 17071번 - 숨바꼭질 5 [Java]

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

 

[백준] 17071번 - 숨바꼭질 5 [Java]

[백준] 17071번 - 숨바꼭질 5 [Java]

---

1.  아이디어

 

이전 숨바꼭질 문제에서 동생이 매초 이동하는 문제로 현재 시간이 짝수인지 홀수인지 구분하는 방식으로 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 1697번 - 숨바꼭질 [Java])

 

수빈이가 5초일 때 10의 위치에 도달할 수 있으면 앞으로 한칸 뒤로 한칸 이동해서 7초에도, 9초에도 10의 위치에 도달할 수 있다. 이를 활용해 동생이 이동한 위치에 수빈이가 도달한 적이 있을 때 현재 시간이 짝수초면 해당 위치에 수빈이도 짝수초에 방문한 적이 있으면 된다. 홀수초도 마찬가지로 수빈이가 해당 위치에 홀수초에 방문한 적이 있으면 이를 통해 구할 수 있다.

---

2. 문제풀이

 

방문한 시간을 기록하는 int 타입 방문 체크 배열을 활용했고 홀수초와 짝수초를 각각 기록했다. 이후 현재 시간이 짝수초면 1초 뒤인 홀수초에 각 위치들을 방문하게 되므로 홀수초 방문 체크 배열을 활용하고 현재 시간이 홀수초면 1초 뒤인 짝수초에 각 위치들을 방문하게 되므로 짝수초 방문 체크 배열을 활용했다. 노드를 꺼냈을 때 동생의 위치와 일치하면 현재 시간을 그냥 반환하면 되고 동생이 이동 중 수빈이가 간 적이 있는 칸을 방문하면 홀짝을 구분해서 조건에 맞으면 반환하게 구현했다. 이전 시리즈의 문제들과 달리 X+1로 이동하는 경우 K 이상도 갈 수 있게 해줘야 했다.

---

3. 코드

 

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

public class Main {

    private static final int MAX = 500_000;

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int time = bfs(N, K);
        System.out.println(time);
    }

    private static int bfs(int N, int K) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(N);

        // 홀수 시간에 대한 방문 체크
        int[] visitedOdd = new int[1 + MAX];
        Arrays.fill(visitedOdd, Integer.MAX_VALUE);

        // 짝수 시간에 대한 방문 체크
        int[] visitedEven = new int[1 + MAX];
        Arrays.fill(visitedEven, Integer.MAX_VALUE);
        visitedEven[N] = 0;

        int time = 0;

        while (!q.isEmpty()) {
            // 찾는 위치가 500,000을 넘어가면 종료
            if (K > MAX) return -1;

            // 홀수 시간에 홀수 시간 방문 체크를 한 경우 또는 짝수 시간에 짝수 시간 방문 체크를 한 경우 가능한 케이스
            if (visitedOdd[K] != Integer.MAX_VALUE && time % 2 == 1) return time;
            if (visitedEven[K] != Integer.MAX_VALUE && time % 2 == 0) return time;

            int len = q.size();

            for (int i = 0; i < len; i++) {
                int node = q.remove();
                if (node == K) return time;

                // 짝수 시간의 이동으로 홀수 시간 방문체크 배열 적용
                if (time % 2 == 0) {
                    // X-1로 이동하려는 경우로 0보다 작은 위치로 이동 X
                    if (node - 1 >= 0 && visitedOdd[node - 1] >= time) {
                        q.add(node - 1);
                        visitedOdd[node - 1] = time;
                    }

                    // X+1로 이동하려는 경우로 500,000보다 큰 위치로 이동 X
                    if (node + 1 <= MAX && visitedOdd[node + 1] >= time) {
                        q.add(node + 1);
                        visitedOdd[node + 1] = time;
                    }

                    // 2*X로 이동하려는 경우로 500,000보다 큰 위치로 이동 X
                    if (node * 2 <= MAX && visitedOdd[node * 2] >= time) {
                        q.add(node * 2);
                        visitedOdd[node * 2] = time;
                    }
                }
                // 홀수 시간의 이동으로 짝수 시간 방문체크 배열 적용
                else {
                    // X-1로 이동하려는 경우로 0보다 작은 위치로 이동 X
                    if (node - 1 >= 0 && visitedEven[node - 1] >= time) {
                        q.add(node - 1);
                        visitedEven[node - 1] = time;
                    }

                    // X+1로 이동하려는 경우로 500,000보다 큰 위치로 이동 X
                    if (node + 1 <= MAX && visitedEven[node + 1] >= time) {
                        q.add(node + 1);
                        visitedEven[node + 1] = time;
                    }

                    // 2*X로 이동하려는 경우로 500,000보다 큰 위치로 이동 X
                    if (node * 2 <= MAX && visitedEven[node * 2] >= time) {
                        q.add(node * 2);
                        visitedEven[node * 2] = time;
                    }
                }
            }

            time++;

            // 동생 위치 이동
            K += time;
        }

        return -1;
    }

}

---

4. 후기