[백준] 18235번 - 지금 만나러 갑니다 (Java)

문제

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

18235번: 지금 만나러 갑니다

 

입력

 

출력

---

알고리즘

너비우선탐색(BFS)

 

일단 만날 수 있는 "최소 일수"를 물어봤다. 즉, 최단 경로를 물어본 것이다. 따라서 이 문제는 깊이우선탐색(DFS)로 풀 수 없다. 최단 경로를 보장하는 것은 BFS이기 때문이다. 찾아보니깐 비트마스킹으로 푸는 사람들도 있지만 그냥 더 단순하고 직관적인 풀이로 설명하겠다.

 

일단 처음에는 특정 지점에 몇일에 도착하는지 기록할 배열을 하나 만든다. 이때, 위치는 최대 n까지이라고 했으므로 배열의 크기는 n+1로 선언하면 된다.

 

그다음, 오리를 a, 육리를 b라고 가정하면 a와 b를 큐에 넣고 동시에 돌린다. 그럼, 내부적으로 우선 a를 먼저 넣었기 때문에 큐니깐 a가 다음날 갈 수 있는 경로가 쫘르륵 기록이 될 것이다. 이때, 더이상 디딜 땅이 없으면 점프를 못한다고 했으므로 범위에 벗어나는지 체크를 해주고 집어넣어줘야 한다.

 

그 다음, a가 큐에서 다 뽑혔으니 이제 b가 갈 수 있는 경로를 쫘르륵 기록 할 것이다. 이 과정에서, 같은 지점에 같은 날짜에 도달하는지 경로를 기록하기 전에 확인해준다. 만약, 같은 지점에 같은 날짜에 도착했다? 그럼 a와 b는 만나는 것이고 BFS는 최단 경로를 보장하기 때문에 그 날이 바로 만날 수 있는 최소 일수가 된다.

 

만약에, 끝까지 못만났다면 더이상 큐에서 꺼낼 것이 없게되고 -1을 return할 것이다. 

---

코드

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 int[] check;
    static int n;
    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());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        
        //특정 지점에 몇일에 도착하는가 기록
        check = new int[n+1];
        System.out.println(bfs(a,b));
    }

    public static int bfs(int a, int b){
        Queue<int[]> queue = new LinkedList<>();
        //a와 b를 동시에 넣고 돌린다. 만약에 a와 b과 같은 지점을 같은 날에 도착한다?
        //그러면 게임 끝이다.
        queue.add(new int[]{a, 0});
        queue.add(new int[]{b, 0});

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            
            //점프할 거리 계산
            int jump = (int) Math.pow(2, cur[1]);

            //오른쪽으로 점프 뛰는 경우
            int first = cur[0] + jump;
            int day = cur[1];
            //갈 수 있는 경우만
            if(first <=n){
                //다음에 갈 경로 계산, 만약에 특정 지점을 같은날 방문 시, 만나는거임.
                if(check[first] == day + 1){
                    return (day + 1);
                }
                //아직 못만나서 큐에 넣고 그 경로에 도달한 날 기록
                else{
                    check[first] = day + 1;
                    queue.add(new int[]{first, day + 1});
                }
            }

            //왼쪽으로 점프 뛰는 경우
            int second = cur[0] - jump;
            //갈 수 있는 경우만
            if(second > 0){
                //위랑 같은 원리
                if(check[second] == day + 1){
                    return (day + 1);
                }
                else{
                    check[second] = day + 1;
                    queue.add(new int[]{second, day + 1});
                }
            }
        }
        //결국에 만나지 못하는 경우
        return -1;
    }
}