1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
1. 문제 분석
- N명의 학생들은 X번 마을까지 갔다가 다시 돌아와야 한다.
- 이때 갔다가 다시 돌아오는 최단 거리를 구해야 한다.
- 각 마을에서 마을로 이동하는 데는 양의 가중치(거리)가 존재한다.
2. 생각해 보기
- 양의 가중치가 존재하기 때문에 다익스트라 아니면 플로이드 와샬을 고려해 본다.
- 플로이드 와샬 알고리즘은 O(N^3)의 시간 복잡도가 필요하다. 마을의 개수(N)가 최대 10^3이기 때문에 플로이드 와샬을 사용하면 최대 10^9의 시간이 걸릴 수 있어 시간 초과가 날 가능성이 있다.
- 그럼 고려해 볼 수 있는 알고리즘은 다익스트라 알고리즘이다.
- 다음은 각 마을에서 X로 가는 최단 거리와, X에서 다시 각 마을로 돌아가는 최단 거리를 구해야 한다.
- 그대로 구현한다면 1, 3, 4 마을에서 각각 2번 마을까지 갈 수 있는 거리를 구해야 한다. 이를 반대로 생각해 보면 다음과 같이 접근해 볼 수 있다.
- (시작 마을) (끝 마을) (거리)를 입력받을 때, 입력받은 대로 저장하는 경우 map과 (끝 마을) (시작 마을) (거리)로 저장하는 경우reverseMap을 모두 저장한다.
- X 마을에서 각 마을(1, 3, 4)로 돌아가는 경우를 구할 때는 map을 사용하면 X 마을을 시작점으로 각 마을로 돌아가는 거리를 구할 수 있다.
- 각 마을(1, 3, 4)에서 X 마을로 가는 경우를 구할 때는 reverseMap을 사용하면 X 마을을 시작점으로 각 마을로 가는 거리를 구할 수 있다.
- 이렇게 reverseMap을 사용하면 X 마을이 도착점이 아닌 시작 마을로 해서 간단하게 다익스트라 알고리즘을 2번 돌려주면 원하는 값을 얻을 수 있다.
3. 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, X;
static List<Node>[] map, reverseMap; // 인접 리스트로 저장
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());
X = Integer.parseInt(st.nextToken());
map = new ArrayList[N + 1];
reverseMap = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
map[i] = new ArrayList<>();
reverseMap[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
map[start].add(new Node(end, dist));
reverseMap[end].add(new Node(start, dist));
}
int[] go = dijkstra(reverseMap); // 각 노드에서 X로 가는 최단 경로
int[] back = dijkstra(map); // X에서 각 노드로 가는 최단 경로
int answer = 0;
for (int i = 1; i <= N; i++) {
answer = Math.max(answer, go[i] + back[i]);
}
System.out.println(answer);
}
public static int[] dijkstra(List<Node>[] inputMap) {
boolean[] visited = new boolean[N + 1];
int[] result = new int[N + 1];
Arrays.fill(result, Integer.MAX_VALUE);
result[X] = 0; // X에서 X로 가는 경로는 0으로 초기화
// 다익스트라 알고리즘 시작
PriorityQueue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.dist - n2.dist);
queue.add(new Node(X, 0));
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (visited[curr.end]) {
continue;
}
visited[curr.end] = true;
for (Node node : inputMap[curr.end]) {
if (curr.dist + node.dist < result[node.end]) {
result[node.end] = curr.dist + node.dist;
}
queue.add(new Node(node.end, result[node.end]));
}
}
return result;
}
static class Node {
int end, dist;
public Node (int end, int dist) {
this.end = end;
this.dist = dist;
}
}
}- 저는 다익스트라 알고리즘에 사용될 map과 reverseMap을 인접리스트 형식으로 저장했습니다.
- PriorityQueue를 사용해서 Node의 dist(거리)를 기준으로 오름차순 정렬되도록 선언했습니다.
- 거리 기준 오름차순으로 저장하면 해당 노드로 도달할 수 있는 최단 거리를 얻을 수 있고, 같은 노드에 대한 정보가 나중에 들어오면 visited를 통해서 contitnue로 걸러줬습니다.
4. 알게 된 점
- 그래프에서 어떤 특정 노드까지 이동을 하고, 다시 되돌아와야 하는 경우가 존재한다면, 해당 특정 노드를 시작점으로 해결해 볼 수 있다는 것을 알게 되었습니다. (입력을 거꾸로 저장, reverseMap)
'🧑🏻💻 Dev > 알고리즘' 카테고리의 다른 글
| [백준] 2206번 벽 부수고 이동하기 (Java) (0) | 2023.06.08 |
|---|---|
| [백준] 1967번 트리의 지름 (Java) (0) | 2023.06.07 |
| [백준] 1931번 회의실 배정 - Java (0) | 2023.05.14 |
| [백준] 1260번 DFS와 BFS 자바 (0) | 2023.04.28 |
| [프로그래머스] 혼자서 하는 틱택토 Java (0) | 2023.03.20 |
