링크
https://www.acmicpc.net/problem/1504
문제 설명
정답률 25.018%
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력 예제
- 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)
- 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000)
- 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)
- 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.
4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3
출력 예제
- 첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
7
풀이
이 문제는 1번 정점에서 임의의 두 정점을 통과하여 N번 정점으로 최단 거리로 이동하여야 하므로 다익스트라 알고리즘(Dijkstra's Algorithm)를 이용하여 최단 경로를 탐색한다.
우선 입력값으로 그래프의 인접 리스트를 구현한다. 입력 예제로 생각해보면 그래프와 인접리스트는 다음과 같다.
다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는데 그 과정에서 이전까지 구했던 최단 거리 정보를 사용한다. 그래서 특정 정점까지의 최단 거리를 구할 수 있는데 이 문제는 특정한 정점을 무조건 통과해야 하므로 문제를 구분하여 생각한다. 1번부터 N번까지 갈 때 v1, v2를 통과해야 한다면
- 1 -> v1
- v1 -> v2
- v2 -> N
이렇게 구분하여 다익스트라 알고리즘을 적용한다. 단, 최소 경로를 구해야하므로 v2 -> v1일 때도 고려해야 한다.
다익스트라 알고리즘은 우선순위 큐를 이용하여 구현한다. 각 노드까지의 거리가 가까운 순서대로 각 노드 마다 최단 거리를 계산해나간다.
코드
//백준
public class Main {
//간선의 최대 개수 20만, 가중치의 최대값 1천
private static final int INF = 200_000_000;
static boolean[] visit;
static int[] dist; //각 정점까지의 최단 거리
static HashMap<Integer, List<Node>> adjList; //인접 리스트
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //정점의 개수
int E = Integer.parseInt(st.nextToken()); //간선의 개수
visit = new boolean[N + 1];
dist = new int[N + 1];
//인접 리스트 초기화
adjList = new HashMap<>();
for (int i = 1; i <= N; i++) {
adjList.put(i, new ArrayList<>());
}
//입력값 세팅
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList.get(start).add(new Node(end, weight));
adjList.get(end).add(new Node(start, weight));
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
//1 -> v1 -> v2 -> N
int r1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N);
//1 -> v2 -> v1 -> N
int r2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N);
int result = Math.min(r1, r2); //최소 비용
//최소 비용이 무한대일 경우 -1 출력
if (result >= INF) {
System.out.println(-1);
} else {
System.out.println(result);
}
}
static int dijkstra(int start, int end) {
//배열 초기화
Arrays.fill(dist, INF);
Arrays.fill(visit, false);
//가까운 순서대로 처리하므로 힙 구조의 우선순위 큐 사용
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(new Node(start, 0));
dist[start] = 0;
while (!queue.isEmpty()) {
Node current = queue.poll();
int curNode = current.end;
if (!visit[curNode]) {
visit[curNode] = true;
//현재 노드의 인접 노드 탐색
for (Node node : adjList.get(curNode)) {
int nextNode = node.end;
//방문한 노드는 패스
if (visit[nextNode]) {
continue;
}
//현재 노드에서 인접 노드로 가는 비용
int nextDist = dist[curNode] + node.weight;
//기존의 최소 비용보다 저렴하다면 갱신
if (dist[nextNode] > nextDist) {
dist[nextNode] = nextDist;
//갱신된 노드를 큐에 추가
queue.add(new Node(nextNode, dist[nextNode]));
}
}
}
}
return dist[end];
}
static class Node implements Comparable<Node> {
int end;
int weight;
public Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
}
}정리
정점 사이의 비용이 모든 같은 그래프에 대한 문제는 풀어봤지만 각각의 비용이 달라 최단 거리를 구하는 문제는 풀어본 적이 없어서 많은 공부가 되었다.
참고
