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

🔺 문제

13549번: 숨바꼭질 3

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;
    static int time = Integer.MAX_VALUE;
    static boolean[] visited = new boolean[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);
        } else {
            System.out.println(bfs());
        }
    }
    
    static int bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(N, 0));
        visited[N] = true;
        
        while(!queue.isEmpty()) {
            Node now = queue.poll();
           
            if(now.x == K) {
                return time = Math.min(time, now.time);
            }
            
            /*** 영역 처리 ***/
            int next;
            // *2 : 꼭 먼저 처리!!
            next = now.x * 2;
            if(next < 100001 && !visited[next]) {
                visited[next] = true;
                queue.add(new Node(next, now.time));
            }
            
            // -1
            next = now.x - 1;
            if(next >= 0 && !visited[next]) {
                visited[next] = true;
                queue.add(new Node(next, now.time + 1));
            }
            
            // +1
            next = now.x + 1;
            if(next < 100001 && !visited[next]) {
                visited[next] = true;
                queue.add(new Node(next, now.time + 1));
            }
        }
        return 0;
    }
}
 
class Node {
    int x, time;
    
    Node(int x, int time) {
        this.x = x;
        this.time = time;
    }
}

✅ 해결 아이디어
✔ BFS
- 세 방향이 동일한 시간이 걸리는 게 아니므로, 위치와 시간 값을 갖는 객체를 하나 만들어 처리
- 그 중에서도 * 2 가장 먼저 처리해야 시간이 더 적게 걸림 !
- 그 자리에서 최솟값 비교해 수 대입

 

---

🔺 다른 풀이들

- next 변수 안 만들고 now.x * 2, now.x + 1, now.x - 1 해서 바로 비교해도 된다.

[백준]13549: 숨바꼭질 3 - JAVA

 

 

- [다익스트라] 내 기준 가장 깔끔한 다익스트라 풀이 같당

[자바]백준 13549번 숨바꼭질3 [그래프-다익스트라][엄탱]

 

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;
    static int time = Integer.MAX_VALUE;
    static boolean[] visited = new boolean[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());
        
        /* 다익스트라 활용 */
        PriorityQueue<int[]> pq = new PriorityQueue<>((x,y) -> x[1] - y[1]); // 오름차순 정렬
        pq.add(new int[] {N, 0});
        
        int cnt = 0;
        while(!pq.isEmpty()) {
            int[] now = pq.poll();
            
            int nowPos = now[0];
            cnt = now[1];
            
            if(nowPos == K) break;
            
            visited[nowPos] = true;
            if(nowPos * 2 <= 100000 && !visited[nowPos * 2])
                pq.offer(new int[] {nowPos * 2, cnt});
                
            if(nowPos < K && nowPos + 1 <= 100000 && !visited[nowPos + 1])
                pq.offer(new int[] {nowPos + 1, cnt + 1});
                
            if(nowPos - 1 >= 0 && !visited[nowPos - 1])
                pq.offer(new int[] {nowPos - 1, cnt + 1});
        }
        
        System.out.println(cnt);
    }
}

 

 

- 다익스트라 정석적 풀이(?) & 해설이 굿

백준 13549, 숨바꼭질 3 - 다익스트라 / BFS

---

💬 느낀 점

잊고 있던 다익스트라를 다시 만나다..ㅋㅋ

 

 

 

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

---

(참고)

 

백준 13549 자바 - 숨바꼭질 3 문제