문제
문제
N개 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력
이후 M번만큼 i번째 도로의 시작점, 끝점, 그리고 소요시간 T
시작점과 끝점이 같은 도로는 없고, 한 도시에서 다른 도시로 가는 도로의 개수는 최대 1개(중복 X)
모든 학생은 X로 갈 수 있고, 오갈 수 있는 데이터만 입력으로 주어짐
출력
가장 오래 걸리는 학생의 소요 시간 출력
풀이
그냥 뺑뺑이를 도는 게 아니고 최단 중에서 제일 오래 걸리는 시간을 구해야 한다. 그러면 각 마을에서 x번째 마을로 도착하는/x번째 마을에서 각 마을로 도착하는 최단 길이를 탐색한 후, 최단 길이 중 max를 구하면 된다!
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int X;
static List<Town>[] go; // 갈 때의 도로 거리를 저장
static List<Town>[] come; // 귀가 할 때의 도로 거리를 저장
static class Town implements Comparable<Town> {
int to;
int cost;
public Town(int to, int cost) {
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Town o) {
return this.cost - o.cost;
}
}
static int[] dijkstra(List<Town>[] list, int start) {
Queue<Town> q = new PriorityQueue<>();
boolean[] check = new boolean[N+1];
int[] dp = new int[N+1];
Arrays.fill(dp, Integer.MAX_VALUE);
q.add(new Town(start, 0));
dp[start] = 0;
while(!q.isEmpty()) {
Town curr = q.poll();
int to = curr.to;
if(check[to]) {
continue;
}
check[to] = true; // 방문 여부
for(Town next : list[to]) {
// 현 도착지까지 + 다음 도착지 < dp[다음 도착지]면 갱신 및 큐에 추가
if(dp[to] + next.cost < dp[next.to]) {
dp[next.to] = dp[to] + next.cost;
q.add(new Town(next.to, dp[next.to]));
}
}
}
return dp;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
go = new ArrayList[N+1];
come = new ArrayList[N+1];
for(int i=0; i<=N; i++) {
go[i] = new ArrayList<>();
come[i] = new ArrayList<>();
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
go[from].add(new Town(to, cost));
come[to].add(new Town(from, cost));
}
int[] goDp = dijkstra(go, X);
int[] comeDp = dijkstra(come, X);
int result = Integer.MIN_VALUE;
for(int i=1; i<=N; i++) {
result = Math.max(result, goDp[i] + comeDp[i]);
}
bw.write(result + "\n");
bw.flush();
bw.close();
br.close();
}
}오는 길과 가는 길이 다르지 않지만, 오고 가는 길의 최단 거리를 각각 구하기 위해 go, come을 따로 작성한다. 입력을 받으며 go와 come에 to, from을 변경해가며 작성한다.
dijkstra 내부에서 go 상태인지 아닌지를 구분하기 쉽지 않기에 그냥 매개변수로 받아서 사용한다. 우선순위 큐와 방문 여부 배열, 메모이제이션용 배열을 생성한다.
큐에 시작하는 마을과 cost를 0으로 잡은 Town을 넣는다.
1. 이후 큐가 빌 때까지 for문을 돌리며
to = 현재 위치에서 가는 곳
2. to를 방문했다고 표시하고, to와 연결되어있는 마을들을 for문을 돌리며
to까지의 cost + 다음 목적지의 cost가 다음 목적지까지의 cost보다 작으면 dp를 갱신하고 큐에 추가한다.
이렇게 하면 dijkstra 함수에서 반환한 배열에는 x로 도착/출발 하는 마을들의 최단 거리가 적힌다. 이후 Math.min() 함수로 최소 거리를 구하고 반환한다.
문제를 풀며
그래프 계열? 문제가 조금 더 직관적인 것 같다.
확실히 개념을 잡아두면 헷갈리는 게 좀 덜한 것 같다.
사실... 저번 주에 이 문제를 읽은 뒤 BFS인가? 라는 생각을 잠깐 했었다. 그 때 이 문제를 바로 풀지는 않았고 오늘 다시 읽고 풀었는데, 그 사이 그래프 관련 개념을 다시 한 번 쭉 잡았었다. 오늘 문제를 다시 읽어보니 절대 BFS일 수 없는 문제였다...! 개념이 정말 중요하다...😭
