백준 10282 (해킹) - java

https://www.acmicpc.net/problem/10282

10282번: 해킹

다익스트라 알고리즘을 사용하여 해결할 수 있다. 다만 중요한 점은 해당 문제의 경우 유독 다익스트라 문제 중에서 메모리관리가 중요한 문제이다. -> 자꾸 메모리 초과가 뜨길래 뭔가 문제가 있나 했는데 문제는 우선순위 큐였다.

 

문제

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();

            if (!visit[cur.v]) {
                visit[cur.v] = true; // 이 코드가 없으면 '메모리 초과'
            }
            else
                continue;
            for (Edge next : graph.get(cur.v)) {
                if (next.c + dis[cur.v] <= dis[next.v]) {
                    dis[next.v] = next.c + dis[cur.v];
                    pq.add(new Edge(next.v, dis[next.v]));
                }

            }
        }

• 다익스트라 알고리즘을 우선순위 큐를 이용하여 구현하는 경우 보통 "방문 배열"을 만들지 않는다. 물론 만들지 않아도 문제를 해결할 수 있다. 하지만 만들지 않을 경우 불필요한 간선에 대한 정보가 우선순위 큐에 탑재될 수도 있다.
• 다익스트라 알고리즘은 "하나의 출발지에서 모든 다른 도착지까지의 최단 거리" 를 구하는 알고리즘이다.
  • 위 굵은 줄의 의미를 통해 방문 처리를 해도 답이 나온다는 것을 이해하는 것이 중요하다.