[백준] 17071번 : 숨바꼭질 5

17071번: 숨바꼭질 5

---

[BFS]

백준의 숨바꼭질 문제 시리즈 중 거의 마지막 문제. 이전의 문제들과는 더욱 꼬아져있다. 수빈이가 움직이는 것은 동일하지만, 이번엔 동생이 움직인다. 그것도 가속도가 붙어서 움직인다. 일반적인 BFS는 한번 방문한 정점에 대하여 다시는 방문하지 않는다.

 

예를 들어 수빈이가 15를 2초만에 도착했다고 하자. 동생이 15를 4초만에 도착했다고 했을 때 일반적인 BFS라면 수빈이는 동생을 금방 만날 수 있음에도 불구하고 저 멀리서 만나거나 만나지 못할 수도 있다.

 

13 5

수빈 : 13, 동생 5 일 때 수빈은 15를 2초에 도착하고, 동생은 15를 4초에 도착한다. 수빈이 동생을 15에서 만나려면 어떻게 해야할까? 다른 곳을 갔다가 다시 15를 오면 된다.

 

즉, 15 - 16 - 15(2s - 3s - 4s)의 경로로 이동하면 수빈은 동생을 4초만에 만날 수 있다. 이처럼 수빈이 이미 지나간 정점에 대해 동생이 뒤늦게 방문했을 때 수빈과 동생은 다시 만날 수 있다. 물론 지금 껏 숨바꼭질 문제를 풀었던 것 처럼 수빈이 처음 방문하는 정점에서 동생을 만나는 것이 가장 쉽게 생각될 수 있다.

 

그럼 수빈이 이미 지나간 정점에 대해 동생이 늦게 방문하면 반드시 둘은 만날 수 있는 것일까?

 

정답은 No 이다. 나는 여기에서 막혔었다. 그러다 질문 게시판을 보다가 해결책을 찾았다. 바로 수빈이 특정 위치 x에 대해 '짝수 시간'과 '홀수 시간'에 도착할 수 있는지를 찾고, 수빈이 x를 방문했다는 가정 하에

동생이 x를 '짝수 시간'에 도착하고, 수빈이 x를 '짝수 시간'에 도착했다면 둘은 만날 수 있는 것이고,

동생이 x를 '홀수 시간'에 도착하고, 수빈이 x를 '홀수 시간'에 도착했다면 둘은 만날 수 있는 것이다.

 

따라서 방문했다는 기록을 남기는 배열을 2차원 배열이 필요하다.

# Code </>

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

public class Main {

    static class Point{
        int cur, target, speed, even;
        public Point(int c, int t, int s, int e){
            cur=c;
            target=t;
            speed=s;
            even = e;
        }
        /*
        * even == 0 짝수
        * even == 1 홀수
        * */
    }
    static int n, k;
    static int[] time[] = new int[500001][2], dir = {-1, 1, 0};
    static boolean[][] visit = new boolean[500001][2];

    static int BFS(){
        Queue<Point> Q = new LinkedList<>();

        visit[n][0] = true;
        Q.add(new Point(n, k, 0, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int cur = p.cur;
            int target = p.target;
            int speed = p.speed;
            int even = p.even;

            if(cur == target)
                return time[target][even];

            dir[2] = cur;
            for(int a=0; a<3; a++){
                int next = cur + dir[a];
                int nTarget = target + (speed + 1);
                int nEven = even == 1? 0 : 1;

                if(next >= 0 && next <= 500000 && nTarget <= 500000) {
                    if(visit[nTarget][nEven]) //동생이 홀수/짝수 시간에 다음 정점에 도착하고 수빈이 홀수/짝수 시간에 다음 정점을 방문했다면
                        return speed + 1;

                    if(!visit[next][nEven]) {
                        time[next][nEven] = time[cur][even] + 1;
                        visit[next][nEven] = true;
                        Q.add(new Point(next, nTarget, speed + 1, nEven));
                    }
                }
            }
        }
        return -1;
    }

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

        System.out.println(k >= 0 && k <= 500000? BFS() : -1);
    }
}

# Reference 

www.acmicpc.net/board/view/35071