Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

25. 최단 경로

그래프의 간선에 가중치가 없으면 BFS로 최단거리를 찾을 수 있습니다. 가중치가 있다면 어떨까요?

Java / Python

3. 미확인 도착지

9370번

최단 거리 알고리즘 응용 문제

이번 문제는 간단하게 정리하면 출발점 -> 도착지 까지의 최단거리 중 특정 간선을 지나는 경우를 구하는 문제입니다.
다익스트라 알고리즘(Dijkstra Algorithm)을 이용합니다.

• Java

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

class Node implements Comparable<Node>{
	int end, weight;

	public Node(int end, int weight){
		this.end = end;
		this.weight = weight;
	}

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

public class Main {
	static final int INF = 10_000_000;
	static int V, E, T;
	static int start, g, h;
	static int[][] graph;
	static int[] dist; 
	static boolean[] check; 
	static List<Integer> resultList; 
    
	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 testcase = Integer.parseInt(br.readLine());
        
		for(int i = 0; i < testcase; i++){
			StringTokenizer st = new StringTokenizer(br.readLine()); 
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());			
			T = Integer.parseInt(st.nextToken());

			// 그래프 배열 선언
			graph = new int[V + 1][V + 1];
			dist = new int[V + 1];
			for(int j = 0; j < graph.length; j++)
				Arrays.fill(graph[j], INF);
			Arrays.fill(dist, INF);
			check = new boolean[V + 1];
            
			// s, g, h 초기화
			st = new StringTokenizer(br.readLine()); 
			start = Integer.parseInt(st.nextToken());
			g = Integer.parseInt(st.nextToken());			
			h = Integer.parseInt(st.nextToken());
            
			// 그래프 정보 저장
			for(int j = 0; j < E; j++){
				st = new StringTokenizer(br.readLine()); 
				int v1 = Integer.parseInt(st.nextToken());
				int v2 = Integer.parseInt(st.nextToken());			
				int distance = Integer.parseInt(st.nextToken());  
                
				graph[v1][v2] = graph[v2][v1] = distance * 2;
			}
            
			graph[h][g] = graph[g][h] = graph[h][g] - 1;
            
			resultList = new ArrayList<>();
			for(int j = 0; j < T; j++)
				resultList.add(Integer.parseInt(br.readLine()));
			dijkstra();
			Collections.sort(resultList);
			for(int num : resultList)
				if(dist[num] % 2 == 1) bw.write(num + " ");
			bw.write("\n");
		}
    
		bw.flush();
		bw.close();
		br.close();
	}

	public static void dijkstra() { 
		PriorityQueue<Node> pqueue = new PriorityQueue<>();
		pqueue.offer(new Node(start, 0));
		dist[start] = 0;

		while (!pqueue.isEmpty()) {
			Node now = pqueue.poll();
			int cur = now.end;
            
			if(!check[cur]){
				check[cur] = true;
                
				for (int i = 1; i <= V; i++) {
					if(!check[i] && dist[i] > dist[cur] + graph[cur][i]){
						dist[i] = dist[cur] + graph[cur][i];            
						pqueue.offer(new Node(i, dist[i]));
					}                             
				}                
			}
		}
	}
}

• Python

from heapq import heappush, heappop
import sys

# dijkstra 경로 탐색
def dijkstra(start):
    dp = [100000000 for i in range(n + 1)]
    dp[start] = 0
    heap = []
    heappush(heap, [0, start])
    while heap:
        we, nu = heappop(heap)
        for ne, nw in graph[nu]:
            wei = we + nw
            if dp[ne] > wei:
                dp[ne] = wei
                heappush(heap, [wei, ne])
    return dp

testcase = int(sys.stdin.readline())
for _ in range(testcase):
    n, m, t = map(int, sys.stdin.readline().split())
    start, g, h = map(int, sys.stdin.readline().split())
    graph = [[] for i in range(n + 1)]
    dist = []
    for j in range(m):
        a, b, d = map(int, sys.stdin.readline().split())
        graph[a].append([b, d])
        graph[b].append([a, d])
    for k in range(t):
        dist.append(int(sys.stdin.readline()))
    start_ = dijkstra(start)
    g_ = dijkstra(g)
    h_ = dijkstra(h)
    resultlist = []
    for l in dist:
        if start_[g] + g_[h] + h_[l] == start_[l] or start_[h] + h_[g] + g_[l] == start_[l]:
            resultlist.append(l)
    resultlist.sort()
    for f in resultlist:
        print(f, end=' ')
    print()