[백준]29140: 가운데에서 만나기 - JAVA
[백준]29140: 가운데에서 만나기

21940번: 가운데에서 만나기
위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.
www.acmicpc.net
풀이
🪑 생각지도 못한 부분에서 헤멨던 문제였다..! 일단 문제를 보자마자 Shortest Path 문제라는 것을 알았고 다익스트라, 플로이드-와샬 알고리즘을 떠올렸다.
📝문제의 조건을 정리해 보자!
- 도시와 도시를 연결하는 간선은 유향(방향성을 가진다)이다.
- 왕복 시간은 A -> B -> A이다.
- 왕복 시간 중 최대가 최소가 되는 도시를 선택한다.
- 여러개인 경우 오름차순으로 출력한다.
🙋♀️ '최대가 최소'에서 이분탐색 힌트를 얻고 처음에는 이분탐색으로 접근하였다.
- 도시별로 왕복 시간을 모두 계산해준 다음, 기준값을 왕복 시간으로 정해준다.
- mid 시간으로 친구들이 살고있는 도시에서 이동할 수 있는 도시가 있는지 확인하며 list를 작성해 주었다.
- 이동할 수 있는 공통된 도시가 존재하면 더 작은시간, 없으면 더 큰시간을 탐색하도록 하였다.
- 일단 이 방법으로 구현하면서 왕복 시간을 계산해 줘야 하는 점과, 이분탐색으로 하나 이상 도달할 수 있는 도시가 있는지 확인하면서 동시에 해당 도시가 조건에 맞는 도시인 X가 될 수 있는지 확인해 주어야 했다.
- 굉장히 복잡하고 불필요한 연산도 많이 포함되었다. 과감히 이분탐색을 버리고 다시 쉽게 생각해 보았다.
🔧 다시 문제의 조건을 따라 풀이 순서를 간략하게 정리해 보자!
- 도시와 도시를 연결하는 최단거리를 구해준다.
- 구한 최단거리를 사용하여 왕복시간 중 최대 값을 찾아준다.
- 최대값 중에서 최소값을 찾아준다.
- 최소값으로 도달할 수 있는 도시를 찾아준다.
- 도시를 오름차순으로 출력한다.
🔹 도시와 도시를 연결하는 최단거리를 구해준다.
- 대표적인 Shortest Path 알고리즘으로는 다익스트라, 플로이드-와샬이 있다.
- 일반적으로 다익스트라는 한 정점에서 모든 정점으로 가는 최단거리를 구할때 사용하고, 플로이드-와샬은 모든 정점에서 모든 정점으로 가는 최단거리를 구할 때 사용한다.
- 이 문제에서는 모든 정점에서 모든 정점으로 가는 최단거리를 구하므로 플로이드-와샬을 사용해 주었다. 물론 다익스트라를 여러번 반복해서 구현해 주어도 된다.
- 단, 주의할 점은 플로이드-와샬은 2차원 배열을 사용해야 하므로 메모리 제한을 확인하고 사용해 주어야 한다.
🔹 구한 최단거리를 사용하여 왕복시간 중 최대값을 찾아준다.
- 플로이드-와샬로 모든 정점간의 최단 거리를 구해주었으니 왕복 시간을 계산하는건 어렵지 않다.
- 도시별로 왕복 시간 중에서 최대값을 찾아 배열로 저장해 주었다.
🔹 최대값 중에서 최소값을 찾아준다.
- 이 문제에서 원하는 정보는 왕복시간들 중 최대가 최소인 값이다.
- 그러므로 최대값들 중에서 최소값을 찾아준다.
🔹 최소값으로 도달할 수 있는 도시를 찾아준다.
- 최소값으로 도달할 수 있는 도시는 왕복 거리의 최대값이 최소값보다 작거나 같은 도시들이다.
- 해당되는 도시들을 list에 담아주었다.
🔹 도시를 오름차순으로 출력한다.
- list에 담긴 결과를 오름차순 정렬하여 출력한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//입력
int n = scan.nextInt();
int m = scan.nextInt();
int INF = n * m + 1;
int[][] dist = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dist[i][j] = INF;
}
dist[i][i] = 0;
}
for(int i = 0; i < m; i++) {
int s = scan.nextInt();
int e = scan.nextInt();
int c = scan.nextInt();
if(dist[s][e] > c) dist[s][e] = c;
}
int k = scan.nextInt();
ArrayList<Integer> city = new ArrayList<>();
for(int i = 0; i < k; i++) {
city.add(scan.nextInt());
}
//입력 끝
//플로이드와샬
for(int l = 1; l <= n; l++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(dist[i][j] > dist[i][l] + dist[l][j]) dist[i][j] = dist[i][l] + dist[l][j];
}
}
}
int[] max = new int[n + 1];
int min = Integer.MAX_VALUE;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < city.size(); j++) {
max[i] = Math.max(max[i], dist[city.get(j)][i] + dist[i][city.get(j)]);
}
min = Math.min(min, max[i]);
}
//최소값으로 갈 수 있는 도시 찾음.
ArrayList<Integer> result = new ArrayList<>();
for(int i = 1; i <= n; i++) {
if(min >= max[i]) result.add(i);
}
Collections.sort(result);
StringBuilder sb = new StringBuilder();
for(int c : result) {
sb.append(c + " ");
}
System.out.println(sb.toString());
}
}
|
cs |