[백준 Java] 17071번 숨바꼭질5 (BFS)

[Platinum V] 숨바꼭질 5 - 17071

문제 링크

성능 요약

메모리: 89244 KB, 시간: 248 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

 

 

 

💡 나의 접근

1. 사람 클래스를 만들어 수빈이와 동생을 boolean 변수로 구분한다.

 

 

2. 동생을 먼저 이동 시킨 후 수빈이를 이동시킨다. 

동생을 이동시킬 때는 즉 큐에 새로운 동생의 위치를 추가할 때에는 현재 초에서 만날 수 있는 경우를 찾지 못했다는 의미이므로 1초를 증가시킨다. 

 

 

3. 수빈이가 이동할 때 같은 타임에 같은 위치은 중복해서 볼 필요가 없지만 다른 타임에 같은 위치는 다시 방문할 수 있다. 

즉 이전에 방문했던 위치를 다시 방문해도 된다는 것이다. 

 

 

4. 수빈이가 짝수초에 도착한 위치는 2초후, 4초후, 6초후 .... 2초 간격으로 다시 재방문 할 수 있어 다시 짝수초에 도착하게 되며

홀수초에 도착한 위치는 역시 2초후, 4초후, 6초후 ... 2초 간격으로 다시 재방문 할 수 있어 다시 홀수초에 도착할 수 있다.

1초에 위치 14에 방문했다면 2초에 15를 방문했다가 3초에 다시 14에 방문이 가능하다. 

2초에 위치 14에 방문했다면 3초에 15, 4초에 14에 방문이 가능하다.

따라서 수빈이가 위치 X에 짝수초에 도착한 이력이 있다면 이후 동생이 짝수초에 위치 X에 도착한다면 그 시간에 맞춰서 왔다갔다 한 후 동생과 맞춰서 도착이 가능하다는 이야기다.

홀수 초 일때도 동일하다.

이를 이용해 짝수초에 위치 X에 도착한 이력과 홀수 초에 위치 X에 도착한 이력을 기록하기 위해서 int 배열 인 evenVisited 배열과 oddVisited 배열을 만들어 두었고 짝수초에 수빈이가 위치 X에 도착했다면 evenVisited 배열에 현재 도착한 초를 기록하도록 하였다. 홀수배열도 동일하다.

이후 동생이 짝수초에 같은위치에 방문했을때 수빈이가 방문했던 이력이 있다면 만날 수 있다는 의미이므로 탐색을 끝냈다. 

 

 

 

 

💡 코드

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

public class Main_17071 {
    static final boolean SUBIN = true;
    static final boolean DONGSAENG = false;
    
    static int N;
    static int K;
    static int time = 0;
    
    static int evenVisited[]; // 위치 n을 방문한 시간이 짝수 시간일때 최초 방문 시간
    static int oddVisited[]; //위치 n을 방문한 시간이 홀수 시간일때 최조 방문 시간
    static boolean meet;
    
    static class Person{
        boolean isSubin;
        int x; // 위치 
        
        public Person(boolean isSubin, int x) {
            super();
            this.isSubin = isSubin;
            this.x = x;
        }
    }


    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);
            return;
        }
        
        evenVisited = new int [500001];
        Arrays.fill(evenVisited, -1);
        oddVisited = new int [500001];
        Arrays.fill(oddVisited, -1);

        Queue<Person> q = new LinkedList<>();

        q.add(new Person(DONGSAENG, K));
        q.add(new Person(SUBIN, N));

        int dongsaengIdx = K;
        Loop1 : while (!q.isEmpty()) {
            Person p = q.poll();
            if(p.isSubin) {// 수빈이가 다음 이동할 위치를 지정할 차례이면

                // 현재 위치의 -1, +1 *2 이동할 위치를 계산해서
                int nextList[] = {p.x -1, p.x+1, p.x*2};

                for (int next : nextList) {
                    //다음 위치가 범위밖을 벗어나면 넘김
                    if(next < 0 || 500000 < next) continue;

                    if(time % 2 == 0 ) { //현재 시간이 짝수
                        if (evenVisited[next] == -1) {
                            evenVisited[next] = time;
                            q.add(new Person(SUBIN, next));
                        }
                    }else { //현재 시간이 홀수
                        if (oddVisited[next] == -1) {
                            oddVisited[next] = time;
                            q.add(new Person(SUBIN, next));
                        }
                    }

                    // 그 위치에 동생이 있는지 확인
                    // 있다면 탐색 끝
                    if(next == dongsaengIdx) {
                        meet = true;
                        break Loop1;
                    }


                }

            }else { // 동생이 다음 이동할 위치를 지정할 차례이면

                // 다음 차례의 수빈이가 도달해야할  동생 위치(dongsaengIdx)을 다음 위치로 변경
                dongsaengIdx = p.x + time +1;
                // 동생이 다음 이동할 위치를 큐에 넣음 현재위치 + time +1;
                if(dongsaengIdx > 500000) {
                    time =-1; //범위가 넘어가면 동생 못만남
                    break;
                }
                time ++; // 탐색 시간을 증가
                if(time % 2 == 0) { 
                    //동생으로 dongsaengIdx에 방문한 시간이 짝수이면
                    if(evenVisited[dongsaengIdx] != -1) {
                        // 수빈이가 그 위치에 짝수시간에 방문한 적이 있는지 확인 있다면
                        meet = true;
                        break;
                    }
                }else {
                    //동생으로 dongsaengIdx에 방문한 시간이 홀수이면
                    if(oddVisited[dongsaengIdx] != -1) {
                        // 수빈이가 그 위치에 홀수시간에 방문한 적이 있는지 확인 있다면
                        meet = true;
                        break;
                    }
                }


                q.add(new Person(DONGSAENG,dongsaengIdx));
            }
        }

        if(meet) {
            System.out.println(time);
        }else {

            System.out.println(-1);
        }


    }
}