Skip to content

Commit 5d11d7c

Browse files
KAispreadKAispread
committed
[Gold II] Title: 면접보는 승범이네, Time: 1332 ms, Memory: 190040 KB -BaekjoonHub
1 parent 7852888 commit 5d11d7c

2 files changed

Lines changed: 144 additions & 0 deletions

File tree

‎백준/Gold/17835. 면접보는 승범이네/README.md‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
# [Gold II] 면접보는 승범이네 - 17835
2+
3+
[문제 링크](https://www.acmicpc.net/problem/17835)
4+
5+
### 성능 요약
6+
7+
메모리: 190040 KB, 시간: 1332 ms
8+
9+
### 분류
10+
11+
데이크스트라, 그래프 이론, 최단 경로
12+
13+
### 제출 일자
14+
15+
2024년 4월 17일 13:06:24
16+
17+
### 문제 설명
18+
19+
<p>마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 <strong>㈜승범이네</strong> 본사가 자리를 잡고 있다. 승범이는 <strong>㈜승범이네</strong>의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.</p>
20+
21+
<p>면접자들은 서로 다른 <em>N</em>개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 <em>N</em>개 도시 중 <em>K</em>개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다.</p>
22+
23+
<p>모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다. 즉, 아래에서 언급되는 '<strong>면접장까지의 거리</strong>'란 그 도시에서 도달 가능한 가장 가까운 면접장까지의 최단 거리를 뜻한다.</p>
24+
25+
<p>속초 출신 승범이는 지방의 서러움을 알기에 각 도시에서 면접장까지의 거리 중, 그 거리가 가장 먼 도시에서 오는 면접자에게 교통비를 주려고 한다.</p>
26+
27+
<p>승범이를 위해 면접장까지의 거리가 가장 먼 도시와 그 거리를 구해보도록 하자.</p>
28+
29+
### 입력
30+
31+
<p>첫째 줄에 도시의 수 <em>N</em>(2 ≤<em> N</em> ≤ 100,000), 도로의 수 <em>M</em>(1 ≤ <em>M</em> ≤ 500,000), 면접장의 수<em> K</em>(1 ≤ <em>K</em> ≤<em> N</em>)가 공백을 두고 주어진다. 도시는 1번부터 <em>N</em>번까지의 고유한 번호가 매겨진다.</p>
32+
33+
<p>다음 <em>M</em>개의 줄에 걸쳐 한 줄마다 도시의 번호 <em>U</em>, <em>V</em>(<em>U</em> ≠ <em>V</em>)와 도로의 길이 <em>C</em>(1 ≤ <em>C</em> ≤ 100,000)가 공백을 두고 순서대로 주어진다. 이는 도시 <em>U</em>에서 <em>V</em>로 갈 수 있는 도로가 존재하고, 그 거리가 <em>C</em>라는 뜻이다.</p>
34+
35+
<p>마지막 줄에 면접장이 배치된 도시의 번호 <em>K</em>개가 공백을 두고 주어진다.</p>
36+
37+
### 출력
38+
39+
<p>첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다.</p>
40+
41+
<p>둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.</p>
42+

‎백준/Gold/17835. 면접보는 승범이네/면접보는 승범이네.java‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
import java.io.BufferedReader;
2+
import java.io.IOException;
3+
import java.io.InputStreamReader;
4+
import java.util.ArrayList;
5+
import java.util.Arrays;
6+
import java.util.HashMap;
7+
import java.util.List;
8+
import java.util.Map;
9+
import java.util.PriorityQueue;
10+
import java.util.Queue;
11+
import java.util.StringTokenizer;
12+
13+
public class Main {
14+
15+
// 단방향 도로를 역방향으로 저장
16+
// 면접장이 배치된 도시에서 다른 모든 도시로 가는 최단 거리에서 가장
17+
// Map<> 에 각 도시의 정보를 저장해놓고 면접장이 배치된 도시에 다익스트라 알고리즘을 K번 사용하면서 최단거리 update
18+
// Map.entry 를 통해 update 된 도시의 정보를 array에 넣고 정렬
19+
20+
static class Edge {
21+
int number;
22+
long dist;
23+
24+
public Edge(int number, long dist) {
25+
this.number = number;
26+
this.dist = dist;
27+
}
28+
}
29+
30+
static final long INF = 100_000_000_000L;
31+
static List<Edge>[] nodes;
32+
33+
public static void main(String[] args) throws IOException {
34+
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
35+
StringTokenizer st = new StringTokenizer(bf.readLine());
36+
37+
int N = Integer.parseInt(st.nextToken());
38+
int M = Integer.parseInt(st.nextToken());
39+
int K = Integer.parseInt(st.nextToken());
40+
nodes = new List[N + 1];
41+
int[] kNodes = new int[K];
42+
43+
for (int i = 1; i < nodes.length; i++) {
44+
nodes[i] = new ArrayList<>();
45+
}
46+
47+
for (int i = 0; i < M; i++) {
48+
st = new StringTokenizer(bf.readLine());
49+
int U = Integer.parseInt(st.nextToken());
50+
int V = Integer.parseInt(st.nextToken());
51+
int dist = Integer.parseInt(st.nextToken());
52+
53+
nodes[V].add(new Edge(U, dist));
54+
}
55+
56+
st = new StringTokenizer(bf.readLine());
57+
for (int i = 0; i < K; i++) {
58+
int n = Integer.parseInt(st.nextToken());
59+
kNodes[i] = n;
60+
}
61+
62+
long[] minimum = dijkstra(kNodes);
63+
64+
long answer = 0;
65+
int number = 0;
66+
for (int i = 1; i < minimum.length; i++) {
67+
if (answer < minimum[i]) {
68+
answer = minimum[i];
69+
number = i;
70+
}
71+
}
72+
73+
System.out.println(number);
74+
System.out.println(answer);
75+
}
76+
77+
private static long[] dijkstra(int[] k) {
78+
Queue<Edge> queue = new PriorityQueue<>((o1, o2) -> (int) (o1.dist - o2.dist));
79+
long[] minimum = new long[nodes.length];
80+
Arrays.fill(minimum, INF);
81+
82+
for (int ks : k) {
83+
minimum[ks] = 0;
84+
queue.offer(new Edge(ks, 0));
85+
}
86+
87+
while (!queue.isEmpty()) {
88+
Edge current = queue.poll();
89+
90+
if (minimum[current.number] < current.dist) continue;
91+
92+
for (Edge next : nodes[current.number]) {
93+
if (minimum[next.number] > current.dist + next.dist) {
94+
minimum[next.number] = current.dist + next.dist;
95+
queue.offer(new Edge(next.number, minimum[next.number]));
96+
}
97+
}
98+
}
99+
100+
return minimum;
101+
}
102+
}

0 commit comments

Comments
 (0)