링크
https://www.acmicpc.net/problem/1238
문제 설명
정답률 48.858%
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+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다.
- 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
- 모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3출력 예제
- 첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
10풀이
다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제에 적용할 수 있다.
이 문제에서는 각 노드에서 노드 X까지의 최단 거리를 구해야 한다. 단, 왕복을 해야하기 때문에 다음의 2가지 경우를 모두 구해야한다.
- 모든 노드 -> X
- X -> 모든 노드
단 다익스트라는 특정 노드에서 시작해야 하기 때문에 X에서 돌아올 때를 구하기 위해서는 역방향 인접 리스트를 따로 생성하여 적용한다.
List<List<Edge>> adjList = new ArrayList<>();
List<List<Edge>> reversedAdjList = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adjList.add(new ArrayList<>());
reversedAdjList.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList.get(start).add(new Edge(end, weight));
reversedAdjList.get(end).add(new Edge(start, weight));
}다익스트라는 우선 최단 거리 배열을 만들어, 시작 노드는 0, 나머지 노드는 아주 큰 값으로 초기화 한다. 그리고 값이 가장 작은 노드에서 시작하여 최단 거리 배열을 갱신해나간다.
static int[] dijkstra(List<List<Edge>> adjList) {
PriorityQueue<Edge> pq = new PriorityQueue<>(comparingInt(Edge::getWeight));
//최단 거리 배열 초기화
int[] dist = new int[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
//X를 시작 노드로 설정
dist[X] = 0;
pq.add(new Edge(X, 0));
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int now = edge.end;
int weight = edge.weight;
if (weight > dist[now]) {
continue;
}
//인접 노드 탐색
for (Edge next : adjList.get(now)) {
int nextWeight = weight + next.weight;
if (nextWeight < dist[next.end]) {
dist[next.end] = nextWeight;
pq.add(new Edge(next.end, nextWeight));
}
}
}
return dist;
}코드
//백준
public class Main {
static int N;
static int X;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
List<List<Edge>> adjList = new ArrayList<>(); //X -> 모든 노드
List<List<Edge>> reversedAdjList = new ArrayList<>(); //모든 노드 -> X
for (int i = 0; i <= N; i++) {
adjList.add(new ArrayList<>());
reversedAdjList.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList.get(start).add(new Edge(end, weight));
reversedAdjList.get(end).add(new Edge(start, weight));
}
int[] fromX = dijkstra(adjList);
int[] toX = dijkstra(reversedAdjList);
int max = 0;
for (int i = 1; i <= N; i++) {
max = Math.max(max, toX[i] + fromX[i]);
}
System.out.println(max);
}
static int[] dijkstra(List<List<Edge>> adjList) {
PriorityQueue<Edge> pq = new PriorityQueue<>(comparingInt(Edge::getWeight));
//최단 거리 배열 초기화
int[] dist = new int[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
//X를 시작 노드로 설정
dist[X] = 0;
pq.add(new Edge(X, 0));
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int now = edge.end;
int weight = edge.weight;
if (weight > dist[now]) {
continue;
}
//인접 노드 탐색
for (Edge next : adjList.get(now)) {
int nextWeight = weight + next.weight;
if (nextWeight < dist[next.end]) {
dist[next.end] = nextWeight;
pq.add(new Edge(next.end, nextWeight));
}
}
}
return dist;
}
static class Edge {
int end;
int weight;
public Edge(int end, int weight) {
this.end = end;
this.weight = weight;
}
public int getWeight() {
return weight;
}
}
}
백엔드