https://www.acmicpc.net/problem/13168
13168번: 내일로 여행
첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소
www.acmicpc.net
문제
친한 친구인 승현이와 지학이는 여름방학 때 여행을 가기로 계획했습니다. 해외여행은 금전적으로 부담이 많기 때문에 둘은 한국의 여러 도시를 여행하기로 했습니다. 한국에는 N개의 도시가 있으며, 승현이는 이 중 여행할 M개의 도시를 결정했습니다. 여행 경로에서 같은 도시를 여러 번 방문할 수 있으며, 여행을 시작하는 도시와 끝내는 도시는 같습니다.
한국에는 두 도시 사이를 오갈 수 있는 K개의 교통수단이 있습니다. 교통수단의 종류는 기차, 지하철, 버스, 택시, 비행기 등으로 다양합니다. 특히 기차 코스는 매우 세부적으로 나뉘어 있어서 무궁화호(Mugunghwa), ITX-새마을(ITX-Saemaeul), ITX-청춘(ITX-Cheongchun), KTX, S-Train, V-Train 등이 있습니다. 모든 교통수단은 한 번 이용하는 데 필요한 비용이 정해져 있습니다. 승현이와 지학이는 계획한 M개의 도시를 최소비용으로 차례대로 움직일 것입니다.
한편, 코레일에서는 ‘내일로’라는 특별한 기차표를 판매하고 있습니다. 방학 동안, 젊은 청년들은 R원을 주고 내일로 티켓을 살 수 있습니다. 한 번 내일로 티켓을 사면, 며칠 동안 무궁화호, ITX-새마을, ITX-청춘은 무료로 이용할 수 있으며, S-Train과 V-Train은 50% 할인된 가격으로 이용할 수 있습니다. KTX나 지하철, 또는 다른 교통수단에 대해서는 할인이 적용되지 않습니다.
지학이는 자신이 아무것도 하지 않는 것에 죄책감을 느끼기 때문에, 자신들의 여행에서 내일로 티켓이 필요한지 생각해보기로 했습니다. 지학이를 도와 내일로 티켓을 사는 것과 사지 않는 것 중 어떤 선택이 더 좋은 지 구하는 프로그램을 작성하세요.
입력
첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소문자로 구성된 길이 20 이하의 문자열입니다. 세 번째 줄에는 승현이와 지학이가 여행할 도시의 수 M(1 ≤ M ≤ 200)이 주어집니다. 네 번째 줄에는 승현이와 지학이가 여행할 M개 도시의 이름이 주어집니다. 이 도시들은 앞서 언급된 N개의 도시 중 하나입니다. 다섯 번째 줄에는 교통수단의 수 K(1 ≤ K ≤ 10,000)가 주어집니다. 마지막 K개의 줄에는 교통수단에 대한 정보가 주어집니다. 줄마다 교통수단의 종류 Typei, 양 끝 도시 Si, Ei, 1인당 비용 Costi (1 ≤ Costi ≤ 100,000)가 주어집니다. Typei는 ‘Subway’, ‘Bus’, ‘Taxi’, ‘Airplane’, ‘KTX’, ‘S-Train’, ‘V-Train’, ‘ITX-Saemaeul’, ‘ITX-Cheongchun’, ‘Mugunghwa’ 중 하나이며, 모든 도시는 주어진 K개의 교통수단을 이용하여 갈 수 있음이 보장되어 있습니다.
한국에는 이름이 같은 도시가 있을 수 있다. 따라서, N개의 도시의 이름에는 같은 도시의 이름이 두 번 이상 주어질 수도 있다. 이 경우 이러한 도시를 모두 같은 도시라고 생각해야 한다.
출력
한줄에 내일로 티켓을 사는 것이 좋으면 ‘Yes’를 출력하고 그렇지 않으면 ‘No’를 출력합니다. 내일로 티켓을 사더라도 비용이 정확히 같다면 ‘No’를 출력합니다.
풀이
티켓을 산 경우, 티켓을 안 산 경우를 각각 따로 담아 플로이드를 돌리고, 각 경로에 대하여 티켓을 산 경우랑 티켓을 안 산 경우 총 비용을 비교하면 된다.
여담으로, 반값을 계산할 때 double형으로 계산해야한다고 한다: 편의를 위해, 가격을 2배 곱하여 저장한 후 결과만 2로 나누었다.
배운 점
1. 플로이드 for문 순서는 k -> i -> j
- 배웠었는데 까먹었다. 'i에서 j로 가는 데 k를 들르는 경우가 더 빠를까?를 모든 k에 대해 본다'라고 이해를 하자.
2. 플로이드를 실행할 이차원 배열의 값을 INF로 초기화하는 과정 필수, 플로이드 연산과정에서 overflow나지 않도록 조심
코드
|
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
import java.io.*;
import java.util.*;
public class Main {
static final int INF = 1_000_000_007;
static int N, R, M;
// idx: 도시 이름 -> 번호, ticketDist: 티켓 사고 가격, dist: 티켓 안 사고 가격
static HashMap<String, Integer> idx = new HashMap<String, Integer>();
static int[][] ticketDist, dist;
static String[] travels; // 여행다닐 도시
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());
R = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
// 같은 이름의 도시 중복 제외하기
int cnt = 0;
for (int i = 0; i < N; i++) {
String city = st.nextToken();
if (idx.containsKey(city)) continue;
idx.put(city, cnt++);
}
N = cnt;
ticketDist = new int[N][N];
dist = new int[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(ticketDist[i], INF);
Arrays.fill(dist[i], INF);
}
M = Integer.parseInt(br.readLine());
travels = new String[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
travels[i] = st.nextToken();
}
int K = Integer.parseInt(br.readLine());
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
String trans = st.nextToken();
int from = idx.get(st.nextToken());
int to = idx.get(st.nextToken());
int d = Integer.parseInt(st.nextToken());
if (trans.equals("ITX-Saemaeul") || trans.equals("ITX-Cheongchun") ||
trans.equals("Mugunghwa")) {
ticketDist[from][to] = 0;
ticketDist[to][from] = 0;
} else if (trans.equals("S-Train") || trans.equals("V-Train")) {
ticketDist[from][to] = Math.min(ticketDist[from][to], d);
ticketDist[to][from] = Math.min(ticketDist[to][from], d);
} else {
ticketDist[from][to] = Math.min(ticketDist[from][to], 2*d);
ticketDist[to][from] = Math.min(ticketDist[to][from], 2*d);
}
dist[from][to] = Math.min(dist[to][from], 2*d);
dist[to][from] = Math.min(dist[to][from], 2*d);
}
double ticket = ((double)floyd(ticketDist)) / 2 + R;
double noTicket = ((double) floyd(dist)) / 2;
System.out.println((ticket < noTicket)? "Yes": "No");
}
static int floyd(int[][] map) {
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][k] + map[k][j] < map[i][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
int ret = 0;
for (int i = 0; i < M-1; i++) {
ret += map[idx.get(travels[i])][idx.get(travels[i+1])];
}
return ret;
}
}
|
cs |
'PS > Floyd-Warshall' 카테고리의 다른 글
| 백준 23258번: 밤편지 (Java) (0) | 2022.06.16 |
|---|---|
| 백준 13141번: Ignition (Java) (0) | 2022.06.16 |
| 백준 13314번: 플로이드에 오타가? (Java) (0) | 2022.06.16 |
| 백준 17182번: 우주 탐사선 (Java) (0) | 2022.06.16 |