[2023-05-24] 백준 9370 미확인 도착지

문제 링크 : https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

성능 요약

메모리: 126336 KB, 시간: 2776 ms

분류

데이크스트라, 그래프 이론

문제 설명

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

---

코드

1) 내가 시도한 코드

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;


public class Main
{

    static ArrayList<Node>[] road;
    static HashMap<Integer, Integer> map;
    static ArrayList<Integer> answer;
    static boolean[] visit;
    static int min;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());

        while(T > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());


            //초기화
            //node n개 만큼 길 생성
            road = new ArrayList[n+1];
            for(int i = 0 ; i < road.length; i++)
                road[i] = new ArrayList<>();
            answer = new ArrayList<>();


            //도로 생성
            for(int i = 0; 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());
                road[a].add(new Node(b,d));
                road[b].add(new Node(a,d));
            }

            //t개의 후보 위치
            int[] can = new int[t];

            for(int i = 0; i < t; i++) can[i] = Integer.parseInt(br.readLine());

            //각 후보 위치에 대해 DFS
            for(int i : can) {
                min = Integer.MAX_VALUE;
                map = new HashMap<>();
                visit = new boolean[n+1];
                DFS(s, i, 0, new HashMap<>());
                Integer getg = map.get(g);
                Integer geth = map.get(h);
                if(getg == null) getg = 0;
                if(geth == null) geth = 0;
                if((getg == h) || (geth == g)) answer.add(i);
            }

            int[] ans =  new int[answer.size()];
            for(int i = 0; i < ans.length; i++) {
                ans[i] = answer.get(i);
            }
            Arrays.sort(ans);
            for(int i : ans) {
                System.out.print(i + " ");
            }
            System.out.println();
            T--;
        }

        bw.flush();
    }

    public static void DFS(int start, int end, int sum, HashMap<Integer, Integer> mapTmp) {
        if(visit[start]) return;

        visit[start] = true;
        if(start == end) {
            //간 거리가 최소라면 최솟값 업데이트
            if(sum < min) {
                min = sum;
                map = (HashMap<Integer, Integer>) mapTmp.clone();
                visit[start] = false;
                return;
            }
        }
        for(Node n : road[start]) {
            mapTmp.put(start, n.e_node);
            DFS(n.e_node, end, sum + n.val, mapTmp);
            mapTmp.remove(start);
        }
        visit[start] = false;
    }

    public static class Node{
        int val;
        int e_node;

        public Node(int e_node, int val) {
            this.e_node = e_node;
            this.val = val;
        }
    }
}

DFS로 풀어봤는데 시간 초과 에러가 나왔다. 다시 시간복잡도를 계산해보니 O(2,000 + 50,000) * 100 * 100이라 최악의 경우 5초가 약간 넘어가는 것 같다.  3초안에 계산이 끝나야 하는데 DFS로는 시간복잡도를 맞추기 어려워보였다. 그래서 시간 복잡도를 다시 계산하여 다익스트라를 사용하였다.

 

다익스트라를 사용할 경우 우선 순위 큐를 활용하여 최적화한다면 O(Elog(V))로 O(50,000 * log(2,000)) 대략 150,000 근처가 됨을 볼 수 있다. 계산한 풀이 방법으로는 테스트케이스마다 3번의 다익스트라가 반복되어야 하므로 여기에 테스트케이스 갯수와 3을 곱해주면

 

150,000 * 3 * 100 = 45,000,000 정도로 0.45초 정도의 시간안에 계산이 완료됨을 알 수 있다.

 

다익스트라 구현에 애를 먹어서 다익스트라 Sudo 코드를 먼저 작성해보았다.

 

다익스트라 수도 코드 ( start ) {
	dist 를 MAX 로 채우기
	dist[start]=0;
	pq.add(new Node(start, 0); // 까지는 ok??

	// 탐색시작
	while(!pq.empty()){
		Node now = pq.poll(); // 가장 가중치가 적은 다음/혹은 현재 노드
		for(연결된 노드들을 탐색){
			// 여기가 중요
			if(다음노드까지 가는 데 걸리는 (지금까지 계산 된)시간보다 now 를 통해서 이동하는 시간이 더 최단 경로이면? ){
				// 우리는 최단경로를 찾는게 목적이므로, 위 if 문을 만족해야만 최단경로를 찾는 목적에 부합
				// 그러므로, 위 if 문을 만족하는 경우에 대해서만
						1. dist[다음노드] 를 갱신
						2. 다음노드에서 또 탐색을 수행
							2-1. pq.add(new Node(다음노드, dist[다음노드));
			}
			// 만약 여기에 2-1. 코드를 넣으면?
				// 그냥 모든 노드를 다 넣게됨. 심지어는 중복 방문이 계속일어나서 무한루프돌것.

		}
	}

}

 

다음은 구현한 코드이다.

 

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;


public class Main
{

    static ArrayList<Node>[] road;
    static PriorityQueue<Node> queue;

    static int min;
    static ArrayList<Integer> answer;
    static int[] dist;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());

        while(T > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());


            //초기화
            //node n개 만큼 길 생성
            road = new ArrayList[n+1];
            for(int i = 0 ; i < road.length; i++)
                road[i] = new ArrayList<>();
            queue = new PriorityQueue<>();
            dist = new int[n+1];


            //도로 생성
            for(int i = 0; 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());
                road[a].add(new Node(b,d));
                road[b].add(new Node(a,d));
            }

            //t개의 후보 위치
            int[] can = new int[t];

            for(int i = 0; i < t; i++) can[i] = Integer.parseInt(br.readLine());

            answer = new ArrayList<>();


            for(int x : can) {
                dij(s);
                int s2g = dist[g];
                int s2h = dist[h];
                int s2x = dist[x];
                dij(g);
                int g2h = dist[h];
                int g2x = dist[x];
                dij(h);
                int h2g = dist[g];
                int h2x = dist[x];

                int s2g2h2x = s2g + g2h + h2x;
                int s2h2g2x = s2h + h2g + g2x;

                if(s2g2h2x > s2h2g2x) s2g2h2x = s2h2g2x;

                //만약 길이 연결되있지 않다면 그냥 제외하자.
                if((s2x == Integer.MAX_VALUE) || (s2g2h2x == Integer.MAX_VALUE) || (s2g2h2x == Integer.MAX_VALUE)) continue;
                if(s2x < s2g2h2x) continue;
                answer.add(x);
            }

            int[] ans = new int[answer.size()];
            for(int i = 0; i < ans.length; i++) {
                ans[i] = answer.get(i);
            }
            Arrays.sort(ans);

            for(int i : ans) {
                System.out.print(i + " ");
            }

            System.out.println();
            T--;
        }

        bw.flush();
    }

    public static void dij(int s) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[s] = 0;
        queue.add(new Node(s, 0));
        while(!queue.isEmpty()) {
            Node n = queue.poll();
            for(Node node : road[n.e_node]) {
                if(dist[node.e_node] > dist[n.e_node] + node.val){

                    dist[node.e_node] = dist[n.e_node] + node.val;
                    queue.add(new Node(node.e_node, dist[node.e_node]));
                }
            }
        }
    }

    public static class Node implements Comparable<Node>{
        int val;
        int e_node;

        public Node(int e_node, int val) {
            this.e_node = e_node;
            this.val = val;
        }

        @Override
        public int compareTo(Node o) {
            return this.val - o.val;
        }
    }
}

 

---

느낀점

 

사실 이 문제도 친구의 도움을 많이 받았다. 다익스트라를 구현하는 법을 조금 더 익혀야 될 필요성을 많이 느꼈던 문제였다.