[BOJ9370] 미확인 도착지 (다익스트라, BFS, 그래프 탐색)

 

 

---

문제 링크

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

9370번: 미확인 도착지

 

문제 풀이 

-  다익스트라 알고리즘

-  시간복잡도 : O(ElogV)

-  s에서 출발하여 주어진 경로 g-h, h-g를 거쳐 최단 거리로 의심되는 노드에 도착하는지 파악하고, 경로를 거쳐 도착했을 경우 형식에 맞춰 출력하는 문제

 

 

처음 2차원 배열(int[][] dist = new int[노드][2]) 로 하여 풀이 하였는데 틀렸다

- 0번 인덱스에는 경로(g - h, h-g)를 거치지 않고 도착한 최소비용

- 1번 인덱스에서 경로(g - h, h-g)를 거쳐 도착한 최소 비용 

객관적으로 내가 너무 어렵게 생각하는 경향이 있다 .. 
기술블로그를 통해 방법을 오늘 또 하나 알게 되었다.

 

 

풀이 1) 간선의 가중치 변경

- g-h 경로의 가중치를 홀수(*2 - 1)로 변경하고, 나머지 가중치를 짝수(*2)로 설정한다.

- g-h 경로를 거쳐서 목적지에 도착할 경우 홀수의 값을 가지게 되고, 아닌 경우 짝수를 가지게 됨

- 다익스트라 한번만 수행

해당 방법의 경우 정말 지니어스 하였다

https://dragon-h.tistory.com/22

[백준 9370 : JAVA] 미확인 도착지 / 다익스트라

 

 

 

 

풀이 2) s 에서 바로 가는 비용과, 구간별 비용(s - g - h - d, s - h - g - d)을 비교하는 방법

1) 시작점 s 에서 다익스트라 한번 실행

2) 시작점 g 에서 다익스트라 한번 실행 

3) 시작점 h 에서 다익스트라 한번 실행 

4) 구한 최단 거리 비용을 가지고 아래 점화식에 따라 조건을 만족할 경우 형식에 맞춰 출력하도록 한다

 (s, d) == min((s, g) + (g, h) + (h,d), (s, h) + (h , g) + (g, d))

 

https://studyandwrite.tistory.com/454

[BOJ] 백준 9370 미확인 도착지 - Python/Java

 

 

 

제출 코드

메모리 초과 의 경우 다익스트라 알고리즘에서 연결된 노드와의 비용 비교 조건문에 = (equal) 이 들어갈 경우 중복 방문으로 큐에 추가되어 발생하는 것으로 추측

 

1번 방식)

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

public class Main {
    
   static StringBuilder sb = new StringBuilder();

    static int T;
    static int n, m, t;
    static int s, g, h;

    static List<Edge>[] adj;

    static class Edge implements Comparable<Edge> {
        int idx;
        int cost;

        public Edge(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge edge) {
            return cost - edge.cost; // 오름차순
        }
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        while(T > 0) {
            T -= 1;

            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 교차로 (노드)
            m = Integer.parseInt(st.nextToken()); // 도로(간선)
            t = Integer.parseInt(st.nextToken()); // 목적지 후보 개수

            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken()); // 출발 노드
            g = Integer.parseInt(st.nextToken()); // 경유 노드 1
            h = Integer.parseInt(st.nextToken()); // 경유 노드 2

            adj = new ArrayList[n + 1];
            for(int i = 1; i <= n; i++) adj[i] = new ArrayList<>();

            for(int i = 1; i <= m; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken()); // 비용

                d *= 2;
                if((a == g && b == h) || (a == h && b == g)) { // 지나 쳐야 하는 간선의 경우 가중치를 홀수로 만듦
                    d -= 1;
                }

                adj[a].add(new Edge(b, d));
                adj[b].add(new Edge(a, d));
            }

            // 후보 노드
            int[] spot = new int[t];
            for(int i = 0; i < t; i++) spot[i] = Integer.parseInt(br.readLine());

            Arrays.sort(spot);

            dijkstra(s, spot);
        }
    }

    static void dijkstra(int start, int[] spot) {
        Queue<Edge> que = new PriorityQueue<>();
        que.add(new Edge(start, 0));

        int[] dist = new int[n + 1];
        Arrays.fill(dist, 20000000);
        dist[start] = 0;

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

            if(dist[cur.idx] > cur.cost) continue;

            for(Edge next : adj[cur.idx]) {
                if(dist[next.idx] > dist[cur.idx] + next.cost) {
                    dist[next.idx] = dist[cur.idx] + next.cost;
                    que.add(new Edge(next.idx, dist[next.idx]));
                }
            }
        }

        for(int i : spot) {
            if(dist[i] % 2 == 1) sb.append(i).append(" ");
        }
        sb.append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
    
}

 

2번 방식)

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

public class Main {
    
   static StringBuilder sb = new StringBuilder();

    static int T;
    static int n, m, t;
    static int s, g, h;

    static List<Edge>[] adj;

    static class Edge implements Comparable<Edge> {
        int idx;
        int cost;

        public Edge(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge edge) {
            return cost - edge.cost; // 오름차순
        }
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        while(T > 0) {
            T -= 1;
            
            // 1. 입력 초기화
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 교차로 (노드)
            m = Integer.parseInt(st.nextToken()); // 도로(간선)
            t = Integer.parseInt(st.nextToken()); // 목적지 후보 개수

            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken()); // 출발 노드
            g = Integer.parseInt(st.nextToken()); // 경유 노드 1
            h = Integer.parseInt(st.nextToken()); // 경유 노드 2

            adj = new ArrayList[n + 1];
            for(int i = 1; i <= n; i++) adj[i] = new ArrayList<>();

            for(int i = 1; i <= m; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken()); // 비용

                adj[a].add(new Edge(b, d));
                adj[b].add(new Edge(a, d));
            }


             // 2. 후보 노드 - 오름차순 정렬 수행
            int[] spot = new int[t];
            for(int i = 0; i < t; i++) spot[i] = Integer.parseInt(br.readLine());

            Arrays.sort(spot); // 오름차순 정렬


            // 3. 다익스트라 수행
            int[] distS = dijkstra(s); // 시작점 s 부터 다른 노드까지 거리
            int[] distG = dijkstra(g); // 시작점 g 부터 다른 노드까지 거리
            int[] distH = dijkstra(h); // 시작점 h 부터 다른 노드까지 거리
            
            
            // 4. s -> 후보 노드로 최단 거리 비용과 s -> g - h -> 후보노드 로 가는 비용이 같은 경우 정답이다
            for(int s : spot) {
                int total = distS[s];

                int s_to_g = distS[g];
                int g_to_h = distG[h];
                int h_to_d = distH[s];

                int s_to_h = distS[h];
                int h_to_g = distH[g];
                int g_to_d = distG[s];

                int value = Math.min(s_to_g + g_to_h + h_to_d, s_to_h + h_to_g + g_to_d);

                if(total == value) sb.append(s).append(" ");
            }

            sb.append("\n");
        }
    }

    static int[] dijkstra(int start) {
        Queue<Edge> que = new PriorityQueue<>();
        que.add(new Edge(start, 0));

        int[] dist = new int[n + 1];
        Arrays.fill(dist, 20000000);
        dist[start] = 0;

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

            if(dist[cur.idx] > cur.cost) continue;

            for(Edge next : adj[cur.idx]) {
                if(dist[next.idx] > dist[cur.idx] + next.cost) { // = (equal)들어갈 경우 메모리 초과
                    dist[next.idx] = dist[cur.idx] + next.cost;
                    que.add(new Edge(next.idx, dist[next.idx]));
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
    
}