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

🔺 문제

1697번: 숨바꼭질

 

🔺 코드

import java.util.*;
import java.io.*;
public class Main {
    static int N, K;
    static int[] arr = new int[100001];
    static int minTime = Integer.MAX_VALUE;
    static int next;
    
    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) { // 수빈이는 -1로만 이동할 수 있음
            System.out.println(N - K);
            return;
        }
        
        BFS();
        System.out.println(minTime);
    }
    
    static void BFS() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(N);
        arr[N] = 1; // 시작점 표시
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            if(minTime < arr[now]) return;
            
            for(int d = 0 ; d < 3; d++) {
                if(d == 0)      next = now + 1;
                else if(d == 1) next = now - 1;
                else            next = now * 2;
                
                if(next < 0 || next > 100000) continue;
                
                if(next == K) {
                    minTime = arr[now];
                    return; // BFS 종료
                }
                
                if(arr[next] == 0 || arr[next] == arr[now] + 1) {
                    queue.add(next);
                    arr[next] = arr[now] + 1;
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ BFS
- 가장 짧은 시간 구하기이므로 BFS 사용

 

---

🔺 다른 풀이들

- 과정 상세하게 보여주셔서 좋고, 테스트값까지 적어주심👍👍👍 (복습용)

[백준/1697/Java] 숨바꼭질 - BFS 풀이

 

- 풀이를 글로 잘 설명해주셨다! 그리고 굳이 min 변수를 사용할 필요가 없다는 걸 보여주심.

[Algorithm] 백준_1697 숨바꼭질 JAVA

 

- 갠적으로 가장 깔끔하다고 생각하는 풀이. 다음에 이렇게 풀어봐야지

[백준] 1697번 숨바꼭질 - Java, 자바

---

💬 느낀 점

나는 "숨바꼭질 2" 문제를 먼저 풀었는데

확실히 "숨바꼭질 1" 문제를 풀고 나서 2를 풀었으면 훨씬 더 빠르게 풀 수 있었을 것 같다.

 

그래도 바로 전에, 숨바꼭질 2 풀었을 때 디버깅해보면서 코드 이해했고,

그거 토대로 이번 문제 코드는 스스로 작성해보려고 해서 그런지

숨바2보다는 훨 빠르게 풀었다..!

 

이래서 많이 풀어보는 게 중요헌 것 같다,,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 숨바꼭질 문제 시리즈...

[백준/JAVA] 12851번: 숨바꼭질 2