728x90
백준 13168 - 내일로 여행
https://www.acmicpc.net/problem/13168


문제
입력
첫 번째 줄: 한국에 있는 도시 수 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개 줄: 교통수단 정보 (종류 Type, 양 끝 도시 S_i, E_i, 1인당 비용 Cost_i (1 <= Cost_i <= 100,000))
모든 도시는 주어진 K개의 교통수단 이용해서 갈 수 있음
/ 이름이 같은 도시가 있을 수 있음
-> N개 도시의 이름에는 같은 도시의 이름 2번 이상 주어질 수 있고 이 경우 모두 같은 도시라고 생각해야 함
출력: 내일로 티켓을 사는 것이 좋으면 Yes / 그렇지 않으면 No
(내일로 티켓 사더라도 비용이 같으면 No)
풀이
도시 이름, 여행 경로 문자열로 주어짐 -> 0 ~ N - 1 정수로 매핑
Map<String, Integer> HM = new HashMap<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
String name = st.nextToken();
if (!HM.containsKey(name)) HM.put(name, HM.size());
}
int[] travel = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
travel[i] = HM.get(st.nextToken());
}
자기 자신으로 가는 경로의 최단 비용 0 / 나머지 `INF`로 초기화
- `double[][] normal`: 일반 비용
- `double[][] rail`: 할인 비용
double[][] normal = new double[N][N];
double[][] rail = new double[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(normal[i], INF);
Arrays.fill(rail[i], INF);
normal[i][i] = 0;
rail[i][i] = 0;
}
양방향 노선 -> 두 방향 모두 `Math.min()`으로 설정
- `normal[a][b]`, `normal[b][a]`
- `rail[a][b]`, `rail[b][a]`
- 열차 종류 -> 무료/할인/정가 => `getRailCost(String type, double cost)`
static double getRailCost(String type, double cost) {
if (type.equals("Mugunghwa") || type.equals("ITX-Saemaeul") || type.equals("ITX-Cheongchun")) return 0;
else if (type.equals("S-Train") || type.equals("V-Train")) return cost / 2.0;
return cost;
}
normal[a][b] = Math.min(normal[a][b], cost);
normal[b][a] = Math.min(normal[b][a], cost);
double railCost = getRailCost(type, cost);
rail[a][b] = Math.min(rail[a][b], railCost);
rail[b][a] = Math.min(rail[b][a], railCost);
모든 쌍 최단 거리(Floyd–Warshall)
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
normal[i][j] = Math.min(normal[i][j], normal[i][k] + normal[k][j]);
rail[i][j] = Math.min(rail[i][j], rail[i][k] + rail[k][j]);
}
}
}
- 일반 여행(`normal`): 각 구간 비용 전부 더함
- 내일로 여행(`rail`): `R`(티켓값) + 할인된 구간 비용들의 합
double normalCost = 0;
double railCost = R;
for (int i = 0; i < M - 1; i++) {
int from = travel[i];
int to = travel[i + 1];
normalCost += normal[from][to];
railCost += rail[from][to];
}
코드
import java.io.*;
import java.util.*;
// 내일로 여행
public class boj_13168 {
static int N, R, M, K;
static final double INF = 1_000_000_000;
static double getRailCost(String type, double cost) {
if (type.equals("Mugunghwa") || type.equals("ITX-Saemaeul") || type.equals("ITX-Cheongchun")) return 0;
else if (type.equals("S-Train") || type.equals("V-Train")) return cost / 2.0;
return cost;
}
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());
Map<String, Integer> HM = new HashMap<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
String name = st.nextToken();
if (!HM.containsKey(name)) HM.put(name, HM.size());
}
M = Integer.parseInt(br.readLine());
int[] travel = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
travel[i] = HM.get(st.nextToken());
}
K = Integer.parseInt(br.readLine());
double[][] normal = new double[N][N];
double[][] rail = new double[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(normal[i], INF);
Arrays.fill(rail[i], INF);
normal[i][i] = 0;
rail[i][i] = 0;
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
String type = st.nextToken();
String s = st.nextToken();
String e = st.nextToken();
double cost = Double.parseDouble(st.nextToken());
int a = HM.get(s);
int b = HM.get(e);
normal[a][b] = Math.min(normal[a][b], cost);
normal[b][a] = Math.min(normal[b][a], cost);
double railCost = getRailCost(type, cost);
rail[a][b] = Math.min(rail[a][b], railCost);
rail[b][a] = Math.min(rail[b][a], railCost);
}
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
normal[i][j] = Math.min(normal[i][j], normal[i][k] + normal[k][j]);
rail[i][j] = Math.min(rail[i][j], rail[i][k] + rail[k][j]);
}
}
}
double normalCost = 0;
double railCost = R;
for (int i = 0; i < M - 1; i++) {
int from = travel[i];
int to = travel[i + 1];
normalCost += normal[from][to];
railCost += rail[from][to];
}
System.out.println(railCost < normalCost ? "Yes" : "No");
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/PriorityQueue] 백준 1781 - 컵라면 (Java) (0) | 2025.12.01 |
|---|---|
| [BOJ/Floyd-Warshall] 백준 1507 - 궁금한 민호 (Java) (0) | 2025.11.28 |
| [BOJ/Floyd-Warshall + DFS] 백준 17182 - 우주 탐사선 (Java) (0) | 2025.11.27 |
| [BOJ/MST] 백준 2887 - 행성 터널 (Java) (0) | 2025.11.27 |
| [BOJ/Dijkstra] 백준 4485 - 녹색 옷을 입은 애가 젤다지? (Java) (0) | 2025.11.20 |