1504 - 특정한 최단 경로[G4]

 

문제

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

1504번: 특정한 최단 경로

 

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

 

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

 

풀이

 

초기에 문제를 제대로 읽지 않고 이전 노드 탐색처럼 DFS를 사용했었다.

이는 매우 비효율적인 로직으로, 다익스트라 알고리즘을 사용해야 한다.

'최단 거리'와 무방향 그래프라는 이야기를 들었을 때 다익스트라를 생각했어야 했다.

 

 

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, E;
    static int V1, V2; //방문해야 하는 노드
    static ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
    static int result = Integer.MAX_VALUE; //최단거리
    public static void main(String[] args) throws IOException {
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	
    	for(int i = 0; i < N; i++) {
    		graph.add(new ArrayList<int[]>()); //그래프 추가
    	}
    	
    	for(int i = 0; i < E; i++) {
    		st = new StringTokenizer(br.readLine());
    		int start = Integer.parseInt(st.nextToken()) - 1;
    		int end = Integer.parseInt(st.nextToken()) - 1;
    		int dist = Integer.parseInt(st.nextToken());
    		graph.get(start).add(new int[] {end, dist}); //시작 노드 추가
    		graph.get(end).add(new int[] {start, dist}); //끝 노드 추가
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	V1 = Integer.parseInt(st.nextToken());
    	V2 = Integer.parseInt(st.nextToken());
    	
    	for(int i = 0; i < N; i++) {
    		dfs(i, new boolean[N], new HashSet<Integer>(), 0); //재귀 실행
    	}
    }
    
    static void dfs(int nowNode, boolean[] visit, HashSet<Integer> checkVisit, int totalDist) {
    	if(totalDist >= result) return; //기저조건 확인
    	visit[nowNode] = true; //방문 처리
    	
    	if(nowNode == V1 || nowNode == V2) checkVisit.add(nowNode); //방문해야 하는 노드
    	if(checkVisit.size() == 2) { //최단거리 갱신
    		result = Math.min(result, totalDist);
    		return; 
    	}
    	
    	//이후 dfs 로직 .. 
    }
}

 

 

문제를 해결하기 위해 다음 방식을 고려하여 풀이하였다.

 

1. 1번 노드에서 시작하여 다익스트라 알고리즘을 사용해 모든 노드까지의 최단 거리를 계산한다.
2. V1과 V2 노드에 대해서도 다익스트라 알고리즘을 각각 실행하여, 각 노드에서 다른 모든 노드까지의 최단 거리를 계산한다.
3. V1을 거쳐 V2로 가는 경로와 V2를 거쳐 V1으로 가는 경로 중 더 짧은 것을 선택한다.
4. 최종적으로 N번 노드까지의 최단 거리를 계산하여 결과를 도출한다.

 

+ 오버플로우 역시 고려해야 한다. 이를 위해 checkOverflow 함수를 도입하였다.

 

풀이는 아래와 같다.

 

풀이

 

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static final int INF = Integer.MAX_VALUE;
    static int N, E;
    static int V1, V2; //방문해야 하는 노드
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    
    static class Node implements Comparable<Node> {
    	int vertex, dist;
    	
    	public Node(int vertex, int dist) {
    		this.vertex = vertex;
    		this.dist = dist;
    	}
    	
    	@Override
    	public int compareTo(Node n) {
    		return this.dist - n.dist;
    	}
    }
    
    public static void main(String[] args) throws IOException {
    	
    	setting(); //입력받기

    	int[] firstDist = dijkstra(0); //0번째 인덱스부터 순회
        int[] distV1 = dijkstra(V1); //V1부터 연결된 모든 노드까지의 최단거리
        int[] distV2 = dijkstra(V2); //V2부터 연결된 모든 노드까지의 최단거리
        
        //최단거리 탐색
        long path1 = checkOverflow(firstDist[V1], distV1[V2], distV2[N - 1]); //시작 -> V1 -> v2 -> N
        long path2 = checkOverflow(firstDist[V2], distV2[V1], distV1[N - 1]); //시작 -> V2 -> V1 -> N
        long result = Math.min(path1, path2);
        
        //오버플로우 고려
        if(result == INF) System.out.println(-1);
        else System.out.println(result);
    }
    
    static int checkOverflow(int a, int b, int c) {
    	int res = a + b + c;
    	if(a == INF || b == INF || c == INF || res < 0) return INF;
    	else return res;
    }
    
    static int[] dijkstra(int startNum) {
    	int dist[] = new int[N];
    	Arrays.fill(dist, INF);
    	dist[startNum] = 0; //시작 위치
    	PriorityQueue<Node> pq = new PriorityQueue<>(); //최단 거리 큐
    	
    	pq.add(new Node(startNum, dist[startNum])); //해당 위치에서 시작(시작 번호, 지금까지 dist)
    	
    	while(!pq.isEmpty()) {
            Node current = pq.poll(); //현재 노드
            int vertex = current.vertex; //이어진 노드(리스트를 불러오는 인덱스)
            
            if (dist[vertex] < current.dist) continue; //최단거리 넘어갈 경우 생략
            
            //이어진 간선들을 전부 탐색
            for (Node neighbor : graph.get(vertex)) {
                if (dist[neighbor.vertex] > dist[vertex] + neighbor.dist) {
                    dist[neighbor.vertex] = dist[vertex] + neighbor.dist;

                    // 해당 방향으로 새로운 노드 추가
                    pq.offer(new Node(neighbor.vertex, dist[neighbor.vertex]));
                }
            }
    	}
    	
    	return dist;
    }
    
    static void setting() throws IOException {
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	
    	for(int i = 0; i < N; i++) {
    		graph.add(new ArrayList<Node>()); //그래프 추가
    	}
    	
    	for(int i = 0; i < E; i++) {
    		st = new StringTokenizer(br.readLine());
    		int start = Integer.parseInt(st.nextToken()) - 1;
    		int end = Integer.parseInt(st.nextToken()) - 1;
    		int dist = Integer.parseInt(st.nextToken());
    		graph.get(start).add(new Node(end, dist)); //시작 노드 추가
    		graph.get(end).add(new Node(start, dist)); //끝 노드 추가
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	V1 = Integer.parseInt(st.nextToken()) - 1;
    	V2 = Integer.parseInt(st.nextToken()) - 1;
    }
    
}