[Java/다익스트라] 백준 13549. 숨바꼭질3

13549번: 숨바꼭질 3

🤔 Intuition

처음에는 DP라고 생각했다. 근데 아니였다.

 

DP가 성립하려면 2가지 조건을 성립해야 한다.

1. 부분 반복 문제 (Overlapping subproblem) : 어떤 문제가 부분 문제로 쪼개질 수 있는지
2. 최적 부분 구조 (optimal substructure) : 부분 문제에서 구한 최적의 답이, 원래 문제의 최적의 답과 동일한지

이 문제를 통해 위 조건을 검토해보자면,

1. 부분 반복은 된다. 왼쪽으로 한칸, 오른쪽으로 한칸 가는 것이 가중치가 1이고, 2배로 점프하는 것이 가중치가 0이라고 할 때, 어떤 연산이 가장 최소의 연산이 되는지 반복적으로 연산한다.
2. 최적 부분 구조를 성립하지 않는다. 이를 성립하기 위해서는 DAG(directed acyclic graph ; 유향 비순환 그래프)여야 한다. 즉, 각 노드의 관계를 정의해볼 때 사이클이 존재하지 않아야 한다. 하지만 이 문제는 조금만 생각해도 알 수 있듯이 2*X 지점과 Y+1 or Y - 1이 일치할 수 있으며, 최소값을 갱신하기 위해서는 "되돌아가는 연산을 수행해야 하는 경우가 발생한다." 쉽게 말해서, 경우에 따라 특정 노드가 정답을 갖는 점화식이 매번 달라짐을 의미한다. 이를 통해 일정한 규칙에 따라 값을 구해나가는 DP가 성립하지 않는다는 것을 이해하고 넘어가야 한다.

위 조건을 피상적으로 이해하고 있었다. 이번 문제를 통해 다시 돌아보게 되는 계기가 되었다.

 

--

 

결과적으로 이 문제는 한 노드에서 목적 노드까지 가중치가 주어진 그래프 상에서 최단 거리를 구하는 다익스트라 문제였다.

 

다익스트라는 "양의 가중치"를 갖는 유/무향 그래프에서 사용 가능하다.

🔎 Algorithm & Complexity

 * @algorithm dijkstra
 * @time O(E * logV) ; 연결된 간선 개수만큼 pq를 이용하여 순회하는 다익스트라 -> 296 ms
 * @memory O(V * E) ; 노드당 엣지 개수 저장하는 list 배열 운영 -> 40744 KB

👨🏻‍💻 Logic

다익스트라 문제라는 걸 깨달으면 문제는 간단해진다. 그냥 냅다 다익스트라 로직으로 구하면 답이 된다.

한 가지 개인적으로 어색했던 점은, 보통은 인접리스트나 인접행렬을 대놓고 주는 문제만 해 봤던 터라 현재 노드로부터 인접리스트를 구성할 때, 인접한 노드와 가중치 규칙에 따라 매번 adj인접리스트를 만들어주면서 진행해줘야 하는 점이 어색했다.

 

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

public class Main {
    public static final int MAX = 100000;
    private static int[] dist = new int[MAX + 1];
    private static List<int[]>[] adjs = new ArrayList[MAX + 1];
    private static Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
    private 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()); // start
        K = Integer.parseInt(st.nextToken()); // end

        for (int i = 0; i <= MAX; i++) {
            dist[i] = (int) 1e9; // INF
            adjs[i] = new ArrayList<>();
        }

        dist[N] = 0;

        pq.add(new int[]{N, 0});

        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            int v = now[0];
            int w = now[1];

            if (v == K) {
                break;
            }

            if (v + 1 <= MAX) {
                adjs[v].add(new int[]{v + 1, 1});
            }
            if (v - 1 >= 0) {
                adjs[v].add(new int[]{v - 1, 1});
            }
            if (v << 1 <= MAX) {
                adjs[v].add(new int[]{v << 1, 0});
            }

            for (int[] adj : adjs[v]) {
                int nv = adj[0];
                int nw = adj[1];

                if (dist[nv] > dist[v] + nw) {
                    dist[nv] = dist[v] + nw;
                    pq.add(new int[]{nv, dist[nv]});
                }
            }
        }

        System.out.println(dist[K]); // answer
    }
}