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

🔺 문제

12851번: 숨바꼭질 2

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;
    static int min = Integer.MAX_VALUE;     // 동생 찾는 가장 빠른 시간
    static int cnt;                         // 동생 찾는 방법 수
    static int next;
    
    static int[] time = new int[100001];    // 해당 위치에 도착 시간 담는 배열
    
    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) {
            System.out.println(N - K);
            System.out.println(1);
            return;
        }
        
        BFS();
        System.out.println(min);
        System.out.println(cnt);
    }
    
    static void BFS() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(N);
        time[N] = 1;    // 시작점 표시
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            // 현재 방문 시간이 최소 시간보다 크면
            if(min < time[now]) return;
            
            for(int i = 0 ; i < 3 ; i++) {
                if(i == 0)      next = now + 1;
                else if(i == 1) next = now - 1;
                else            next = now * 2;
                
                if(next < 0 || next > 100000) continue;
                
                if(next == K) {
                    min = time[now];
                    cnt++;
                }
                
                // 첫 방문이거나
                // 이미 방문한 곳이어도 같은 시간에 방문했다면
                // 큐에 다시 추가
                if(time[next] == 0 || time[next] == time[now] + 1) {
                    queue.offer(next);
                    time[next] = time[now] + 1;
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ BFS
- int 배열 : 해당 위치에 도착 시간 담는 배열 (time[pos] = sec : pos 위치에서 sec초 만에 도착한 시간) 

 

💥 유의사항

• 해당 위치의 visit 여부 확인을 시간으로 비교해 중복적으로 허용해 줘야 함.

(-1 , +1, *2일 때 다른 경로로 도착할 수 있으므로)

 

 

---

🔺 다른 풀이들

- 상세 설명 굿... (복습용)

[백준] 12851_숨바꼭질2 (자바 JAVA)

 

 

 

---

💬 느낀 점

우왓....

좌표 이동은 이동 방향 배열을 만들어 놓고

좌표 이동 가능한 방향 수만큼 for문을 돌려서 값 이동을 하면 되는구나

 

x축 하나로만 이동하면 되길래 만만하게 보았는데.....

 

숨바꼭질 시리즈를 마스터해야겠다...

 

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

---

(참고)

백준 12851번. 숨바꼭질 2 (Java)

[Java] 백준 12851번 [숨바꼭질2] 자바

[백준] 12851. 숨바꼭질 2 (JAVA)