개요
파티
다익스트라 기본 문제
이 문제에서 조금 헷갈렸던 부분은 파티를 마치고 돌아가는 걸 구현하는 부분이었다.
문제를 보면서 어떻게 해야하는지 분석해보자
문제분석
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
그래프 정의 : N개의 노드가 존재하고, M개의 간선이 존재한다 여기에서 i번째 길을 지나는데 들어가는 시간은 T(i)가 걸린다.
구해야하는 것 : 각각의 학생들이 최단시간에 오고갈때, 거기에서 소요시간이 큰 학생의 소요시간
각각의 학생들은 최단시간에 오고간다 -> 그래프에 가중치(길을 지나는데 소요되는 시간,시간은 음수가 될 수 없다)가 가장 작은 최단경로를 찾아야 한다는 것
즉,이러한 각각의 주어진 조건을 통해 다익스트라 알고리즘을 사용해야한다는 사실을 도출했다.
여기에서 가장 어려웠던 부분은 학생들이 왕복을 한다는 사실을 구현하는 것이었다.
예제의 경우
- 파티에 참여하러가는 길
1 -> 2
3 -> 2
4 -> 2 - 각자 집에 돌아가는 길
2 -> 1
2 -> 3
2 -> 4
이렇게 두개의 경로를 계산해주어야 한다.
이 경로를 잘 살펴보면 공통점이 있다. 하나의 점으로 모이거나, 하나의 점에서 시작하거나 두가지의 경우를 가진다.
우리가 평소 사용하는 다익스트라 알고리즘의 경우
시작지점에서 어떤 도착지점으로 가는게 가장 최소비용을 사용하여 도착하는지를 구한다.
즉,어디에 도착하는지는 정해져있지 않고. 시작지점만 정해져 있다.
이 사실을 생각하면, 파티에 참여하러가는 길의 경우 주어진 인접리스트를 거꾸로 해주면
시작점을 2로하여 다익스트라 알고리즘을 이용해 값을 구할 수 있다.
이외의 모든 것은 다익스트라 알고리즘 기본코드와 동일하기 때문에 이해가 가지 않을 경우 다익스트라 알고리즘을 먼저 이해하고 오는 것을 추천한다.
문제풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* @author onyoo
* @performance
* @category
* @note
* 다익스트라 알고리즘
* 1.가중치의 값이 양수
* 2.최소 시간을 가지면서 최단거리로 가야한다는 점
* 중요한 점
* 모두가 하나의 정점으로 도착하고,하나의 정점에서 시작한다는 점을 생각하면
* 인접리스트를 두개로 만들어야 한다는 생각을 할 수 있다.
* 1 -> 2 , 3 -> 2 ...
* 2 -> 1 , 2 -> 3 ...
* 이 두개의 경우는 정확하게 반대이다, 이것을 이용해서 시작정점과 도착정점을 바꿔준 reverse 인접리스트가 필요
* @see
* https://www.acmicpc.net/problem/1238
* @since 2023-10-17
**/
public class 파티 {
static class Node implements Comparable<Node>{
int idx,time;
public Node(int idx, int time) {
this.idx = idx;
this.time = time;
}
@Override
public int compareTo(Node o) {
return time - o.time;
}
}
static int N,M,X;
static ArrayList<Node>[] adjList;
static ArrayList<Node>[] adjListR;
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());
M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
adjList = new ArrayList[N+1];
adjListR = new ArrayList[N+1];
for(int i=0;i<N+1;i++) {
adjList[i] = new ArrayList<>(); //인접 리스트 초기화
adjListR[i] = new ArrayList<>();
}
for(int i=0;i<M;i++){
st = new StringTokenizer(br.readLine()," ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
adjList[s].add(new Node(e,t));
adjListR[e].add(new Node(s,t));
}
int answer = 0;
int[] dist1 = bfs(adjList);
int[] dist2 = bfs(adjListR);
//reverse list를 만드는 이유
// 하나의 노드 -> 여러노드로 가야하는데,다익스트라의 경우
// 여러 노드 -> 하나의 노드로 갈때 최단거리비용을 구하기 때문에
// 여기 에서 대상 인접리스트의 형태만 바꿔주면 되기 때문이다 그것이 바로 노드 출발 도착점 뒤집기!
for(int i=1;i<N+1;i++){
answer = Math.max(dist1[i] + dist2[i],answer);
}
System.out.println(answer);
}
static int[] bfs(ArrayList<Node>[] adj){
Queue<Node> que = new PriorityQueue<>();
int[] answer = new int[N+1];
Arrays.fill(answer,987654321);
que.add(new Node(X,0)); // 지금 시작합니다.
answer[X] = 0; //도착지로 들어오는건 0
while(!que.isEmpty()){
Node curr = que.poll();
for(Node node : adj[curr.idx]){
if(curr.time + node.time < answer[node.idx]){
answer[node.idx] = curr.time + node.time;
que.add(new Node(node.idx,answer[node.idx]));
}
}
}
return answer;
}
}