[BAEKJOON]1504 특정한 최단 경로

문제 요약

• 알고리즘 분류: 다익스트라
• 난이도: Gold4
• 문제내용:
  • 1 부터 N까지 v1, v2 거쳐서 최단 경로를 구해라
• 사이트: https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

문제풀이

   이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 

문제 접근 방법

 이번문제는 1 → N까지 최단 경로를 구하는 알고리즘인데 조건이 중간에 2개 노드를 지나가야 한다는 점이다. 중간에 2개의 노드를 지나가야 하는데 나올수 있는 경우의 수는 2가지 이다.

1. 1 → v1 → v2 → N
2. 1 → v2 → v1 → N

위 2가지 경우의 수중 최소값만 출력하면 끝이다. 어떻게 풀어야 할지 알았으면 마지막은 구현이다. 구현하는 방법은 1 부터 중간 노드까지 다익스트라 알고리즘으로 구현하고 중간 노드부터 N까지 다익스트라 알고리즘을 구해서 더하기만 된다.

이번 문제도 다익스트라 알고리즘 구현만 할줄 알면 풀이와 구현 방법은 쉽기 때문에 자세하게는 설명 안하겠다.

Code

Python

import sys, heapq
input = sys.stdin.readline
INF = 1e9

def dijkstra(start, end):
    distances = [INF] * (N + 1)
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        now_distance, now_node = heapq.heappop(queue)
        if now_distance > distances[now_node]: continue
        for node, weight in grape[now_node]:
            distance = now_distance + weight

            if distances[node] > distance:
                distances[node] = distance
                heapq.heappush(queue, (distance, node))

    return distances[end]


N, M = map(int, input().split())    
grape = {i: [] for i in range(1, N + 1)}


for _ in range(M):
    a, b, T = map(int, input().split())
    grape[a].append([b, T])
    grape[b].append([a, T])


v1, v2 = map(int, input().split())

result = min(dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N), dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N))

print(result if result < INF else -1)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N, M;
	static Map<Integer, List<Integer>> grape = new HashMap<>();
	static int[] distances;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());

		distances = new int[N + 1];

		for(int i = 1; i <= N; i++){
			grape.put(i, new ArrayList<Integer>());
		}

		int x, y;
		for(int i = 0; i < M; i++){
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			grape.get(x).add(y);
		}

		BFS(X);
		List<Integer> result = new ArrayList<>();
		for(int i = 1; i <= N; i++){
			if(distances[i] == K){
				result.add(i);
			}
		}
		if(result.isEmpty()){
			System.out.println(-1);
		}else{
			result.forEach(System.out::println);
		}

	}

	public static void BFS(int start){
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);

		int now;
		while (!queue.isEmpty()){
			now = queue.poll();
			for(int node : grape.get(now)){
				if(distances[node] == 0 && node != start){
					distances[node] = distances[now] + 1;
					queue.add(node);
				}
			}
		}

	}
}