[백준 1697] 숨바꼭질 (JAVA)

백준 1697번 문제 - 숨바꼭질

1697번: 숨바꼭질

---

 

문제 분석

 

 

• 내 위치(N)와 동생 위치(K)가 주어졌을 때, 동생을 찾을 수 있는 가장 빠른 시간을 출력해라
• 내가 움직일 수 있는 방법(1초에)
  • X + 1
  • X - 1
  • X * 2

---

 

해결 키 포인트

 

• 갈 수 있는 방법을 다 했을 때 ! 가장 짧은 시간을 알아내야하므로 모든 방법을 탐색하되 정답에 도착하면 종료해야함
  → BFS 사용
• 처음 위치를 큐에 넣고, 반복하면서 갈 수 있는 방법을 모두 큐에 삽입
• 방문확인을 안할 경우 메모리 초과 발생 → 방문확인 필요 ! (visited)
• 큐에 담겨져 있는 모든 경우의 수를 확인했을 경우 count 증가
  + 마지막에 정답에서 -1 필요 (정답이 나와서 count 증가가 필요 없을 때에서 증가가 발생하므로)

---

 

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static int N, K;
    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(BFS());
    }

    static public int BFS() {
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean [] visited = new boolean[100001];

        queue.add(N);
        visited[N] = true;

        while(!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                int value = queue.poll();

                // 동생을 찾은 경우
                if (value == K) {
                    queue.clear();
                    break;
                }
                // 뒤로 걷기
                if (value - 1 >= 0 && !visited[value - 1]) {
                    queue.add(value - 1);
                    visited[value - 1] = true;
                }
                // 앞으로 걷기
                if (value + 1 <= 100000 && !visited[value + 1]) {
                    queue.add(value + 1);
                    visited[value + 1] = true;
                }
                // 순간이동
                if (value * 2 <= 100000 && !visited[value * 2]) {
                    queue.add(value * 2);
                    visited[value * 2] = true;
                }
            }
            count++;
        }

        return count - 1;
    }

}