백준 13549번 : 숨바꼭질 3 자바

🧫 문제 분석

 

✔️ 출처

숨바꼭질 3 골드 5

 

📖 문제

 

bfs는 가중치가 같으면 항상 최단거리이다.

 

• x - 1, x + 1, x * 2 로 x가 k가 될 때까지 이동한다.
• n >= k 일 시 (x - 1) 로만 k로 갈 수 있기에  이를 고려한다. 정답 : n - k
• n과 k 는 0 ~ 100,000 사이이다. 
• x - 1, x + 1, x * 2 인 노드를 bfs로 x(수빈)이가 k(동생)을 찾을때까지 반복하여 탐색한다. 

 

 

---

🔅 문제 풀이

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

public class Main {
    static class Node {
        int cur, cost;

        public Node(int next, int cost) {
            this.cur = next;
            this.cost = cost;
        }
    }
    
    static boolean[] visited;
    static int answer = 100000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        if (n >= k) {
            System.out.println(n - k);
            return;
        }

        visited = new boolean[100001];

        bfs(n, k);
        System.out.println(answer);

    }

    private static void bfs(int start, int k) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(start, 0));

        while (!q.isEmpty()) {
            Node node = q.poll();
            if (visited[node.cur]) continue;

            if (node.cur != k) {
                visited[node.cur] = true;

                // 순간이동
                int nextNode2 = node.cur * 2;
                if (nextNode2 < visited.length && !visited[nextNode2])
                    q.add(new Node(nextNode2, node.cost));

                // -1 칸 이동
                int nextNode = node.cur - 1;
                if (nextNode >= 0 && !visited[nextNode])
                    q.add(new Node(nextNode, node.cost + 1));

                // +1 칸 이동
                int nextNode1 = node.cur + 1;
                if (nextNode1 < visited.length && !visited[nextNode1])
                    q.add(new Node(nextNode1, node.cost + 1));

            } else {
                answer = node.cost;
                return;
            }
        }
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1. 최솟값을 찾을 때 큰 값을 처리해주는 로직을 먼저 두자.
2. 그 외에도 항상 큰 값 먼저 처리하고 그 후에 작은 것을 처리