[백준]17071_숨바꼭질5

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

 

풀이
- 수빈이가 도착하는 시간을 홀/짝으로 구분하여 기록 
- 동생이 수빈이가 방문한 곳에 방문하면 그 시간을 반환 
- 짝/홀 나누는 이유: 동시에 같은 위치에서 만나는지 확인하기 위함

방문체크를 홀짝초 구분하지 않고하면, 답을 구하지 못함
짝수초에 도착해서 홀수초에 도착을 못하게 하는 상황때문
그 지점에 도착한 시간에 따라 동생이랑 겹치는지를 정확히 알수있음

package BJ;

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 BJ_17071_숨바꼭질5 {
    static int n, k;
    static final int LIMIT = 500000;

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

    }

    private static void bfs() {
        Queue<Info> q = new LinkedList<>();
        boolean v[][] = new boolean[500001][2];
 
        q.offer(new Info(n,k,0));
 
        while(!q.isEmpty()){ //
            Info cur = q.poll();
//            System.out.println(cur.toString());
            // 제한시간에 못잡으면 끝난거.
            if(cur.kp>LIMIT || cur.np>LIMIT){
                System.out.println(-1);
                return;
            }
            
            // 동생이 수빈이가 있을 수 있는 위치에 방문한 시점
            if(v[cur.kp][(cur.t)%2]){
                System.out.println(cur.t);
                return;
            }

            // 수빈이는 순간이동을 현위치*2 만큼 이동할 수 있다.
            // 동생은 항상 현위치 + 시간 만큼 이동한다.
            if(cur.np*2 <= LIMIT && !v[cur.np*2][(cur.t+1)%2]){
                q.offer(new Info(cur.np*2,cur.kp+cur.t+1,cur.t+1));
                v[cur.np*2][(cur.t+1)%2] = true;
            }
            if(cur.np+1 <= LIMIT && !v[cur.np+1][(cur.t+1)%2]){
                // 혹은 수빈이가 1보 앞으로 이동
                q.offer(new Info(cur.np+1,cur.kp+cur.t+1,cur.t+1));
                v[cur.np+1][(cur.t+1)%2] = true;
            }
            if(cur.np-1 >=0 && !v[cur.np-1][(cur.t+1)%2]){
                // 혹은 수빈이가 1보 후퇴
                q.offer(new Info(cur.np-1,cur.kp+cur.t+1,cur.t+1));
                v[cur.np-1][(cur.t+1)%2] = true;
            }
        }

        System.out.println(-1);
    }
	
    // 제한시간안에 있는지 확인
    private static boolean isIn(int np){
        return 0<= np && np<500001;
    }

    private static class Info {
        int np, kp, t; // 수빈위치, 동생위치, 시간

        public Info(int np, int kp, int t) {
            this.np = np;
            this.kp = kp;
            this.t = t;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "np=" + np +
                    ", kp=" + kp +
                    ", t=" + t +
                    '}';
        }
    }
}

 

BFS는 마스터한 줄 알았는데.. 오만한 생각이었다. 아직도 갈 길이 멀다. 코테 뚫는 그날까지..