[백준 1697 : JAVA] 숨바꼭질 / BFS

개요

 

BFS는 최단거리를 구하는 경우 가중치가 1일 때 사용할 수 있다.

이 문제는 동생과 형의 시작 지점이 같을 경우 반례 때문에 삽질 좀 했다.

자신 스스로 반례를 찾는 습관을 가지는 것을 추천한다!

 

문제

 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력

 

풀이

 

1. 형의 시작지점을 큐에 추가하고 방문처리를 한다.

 

2. 큐에서 노드를 꺼낸다.

 

3. 꺼낸 노드에서 + 1, - 1, * 2 지점의 유효성 검사를 한다.

       (유효성 검사는 1. 해당 노드 좌표의 유효성 2. 미 방문한 곳인지 를 확인한다.)

 

4. 유효한 경우 큐에 노드를 추가하고 방문처리한다. (이때 기존의 노드 값 + 1을 저장하여 일수를 계산한다.)

 

5. 큐가 비거나 꺼낸 노드의 값 = 동생의 위치 일때까지 2 ~ 4를 반복한다.

 

6. 반복문을 탈출했을 때 isVisit[]의 값 - 1을 출력한다. (시작점을 1로 잡았기 때문에 걸린 일수를 계산하기 위해서는 -1을 해줘야 한다.)

 

코드

 

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 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, k;
    static int isVisit[];
    static Queue<Integer> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        isVisit = new int[100_001];

        int answer = solve();
        System.out.println(answer);
    }
    public static int solve(){
        int result = -1;
        // 형의 시작 노드 큐에 추가
        queue.add(n);
        // 방문 처리
        isVisit[n] = 1;

        while (!queue.isEmpty()){
            int location = queue.poll();
            // 큐에서 꺼낸 값이 동생의 위치인 경우
            if(location == k) {
                result = isVisit[location];
                break;
            }

            if(checkLocation(location - 1)){
                queue.add(location - 1);
                isVisit[location - 1] = isVisit[location] + 1;
            }
            if(checkLocation(location + 1)){
                queue.add(location + 1);
                isVisit[location + 1] = isVisit[location] + 1;
            }
            if(checkLocation(location * 2)){
                queue.add(location * 2);
                isVisit[location * 2] = isVisit[location] + 1;
            }
        }
        // 시작점을 1 초 걸린다고 잡았으므로 -1 한 값을 반환
        return result - 1;
    }

    private static boolean checkLocation(int i) {
        if(i < 0 || i > 100_000) return false;

        if(isVisit[i] > 0) return false;
        else return true;
    }
}