[코테] 백준 1697 숨바꼭질: BFS Java

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

 

우선 문제를 이해하는 게 중요하다.

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

간과하지 말아야 할 포인트.

1) 수빈이가 동생보다 앞에 있을 수 있다.

2) -1 되는 경우도 생각해야 한다. (인덱스가 넘어갈 수 있음.)

 

전체 코드

* 아래 코드 간단 설명 있음

import java.awt.*;
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 baekjoon_1697 {
    private static int N, K;
    private static final int MAX = 100001;
    private static int[] check;

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken()); // 수빈이의 위치
        K = Integer.parseInt(st.nextToken()); // 동생의 위치

        check = new int[MAX];

        if (N == K) {
            System.out.println(0);
        } else {
            bfs();
        }
    }

    static void bfs(){
        Queue<Integer> que = new LinkedList<>();

        que.add(N);
        check[N] = 0;

        while(!que.isEmpty()){
            Integer currentSpot = que.poll();

            for(int i =0; i<3; i++){
                int nextSpot = currentSpot;
                if(i==0) {
                    nextSpot = nextSpot + 1;
                } else if (i==1) {
                    nextSpot = nextSpot - 1;
                } else {
                    nextSpot = nextSpot * 2;
                }

                if(nextSpot >= 0 && nextSpot < MAX && check[nextSpot] == 0) {
                    check[nextSpot] = check[currentSpot] + 1;

                    if(nextSpot == K) {
                        System.out.println(check[nextSpot]);
                        return;
                    }

                    que.add(nextSpot);
                }
            }
        }
    }

}

 

처음에는 MAX를 사용하지 않고 아래와 같이 사용했다.

check = K >= N? new int[K + 1] : new int[N + 1];

이는 2번을 간과한건데, 

예를 들어 수빈이가 10에 있고 동생이 19에 있을 경우 

*2 후 -1을 하는게 가장 빠른 방법으로 인덱스 20을 방문하게 될수도 있기 때문이다.

 

그래서 MAX값을 사용한다. MAX값을 사용해도 동일한 문제가 발생하게 되는 것 아닌가 싶겠지만, BFS는 그 전에 K에 도달하기 때문에 안전하다.

 

nextSpot은 아래와 같이 for문을 이용해서 구할 수도 있다.

for (int nextSpot : new int[]{currentSpot - 1, currentSpot + 1, currentSpot * 2})

나는 for문을 돌릴 때마다 int[]을 생성하는 게 좋지 않다고 봐서 그냥 if문을 이용했다.