백준 1238번 파티 (Java)
April 04, 2021
백준의 G3 문제인 1238번 파티 를 풀어봤다.
조건
- 시간 제한 : 1초
- 메모리 제한 : 128 MB
문제
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에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
예제 입력
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예제 출력
10풀이
각 학생의
(1) (파티장 X) → (각자의 집)
(2) (각자의 집) → (파티장 X)
을 오가는 시간을 더해서 최댓값을 갖는 학생의 왕복 소요시간을 구하면 된다.
경로는 단방향이기 때문에 (각자의 집) → (파티장) 의 소요시간과 (파티장) → (각자의 집) 의 소요시간은 다를 수 있다.
Dijkstra를 사용해서 풀면 된다.
3가지 풀이로 풀어나가면서 메모리와 시간을 개선했다.
공통
필요한 값들을 static하게 선언해준다.
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder output = new StringBuilder();
static StringTokenizer tokens;
static int N, M, X, round[], go[], u, v, w, answer;
static List<Edge>[] list;
static List<Edge>[] list2; // Sol.3에서만 필요
static boolean[] visited;
static PriorityQueue<Vertex> queue = new PriorityQueue<>();우선 간선(Edge)과 정점(Vertex) 클래스를 다음과 같이 생성한다.
정점은 비용의 비교를 위해 compareTo를 오버라이드했다.
static class Edge{
int v;
int w;
public Edge(int v, int w) {
super();
this.v = v;
this.w = w;
}
}
static class Vertex implements Comparable<Vertex>{
int x;
int cost;
public Vertex(int x, int cost) {
super();
this.x = x;
this.cost = cost;
}
@Override
public int compareTo(Vertex o) {
return Integer.compare(this.cost, o.cost);
}
}Solution 1
(2) (각자의 집) → (파티장 X) 를 구할 때 모든 지점에서 다익스트라를 돌림
int[] round = new int[N+1] 배열을 만들어서 각 인덱스에 (파티장 X) ↔ (각자의 집)의 왕복 시간을 저장함
// X에서 집 가는 길
Arrays.fill(round, Integer.MAX_VALUE);
queue.offer(new Vertex(X, 0));
round[X] = 0;
while(!queue.isEmpty()) {
Vertex tmp = queue.poll();
if(visited[tmp.x]) continue;
visited[tmp.x] = true;
for(Edge e: list[tmp.x]) {
round[e.v] = Math.min(round[e.v], tmp.cost+e.w);
if(!visited[e.v]) {
queue.offer(new Vertex(e.v, round[e.v]));
}
}
}
// 각 지점에서 X에 가는 길
for(int i=1; i<N+1; i++) {
if(i==X) continue;
for(int b=0; b<visited.length; b++) {
visited[b] = false;
}
Arrays.fill(go, Integer.MAX_VALUE);
queue.offer(new Vertex(i, 0));
go[i] = 0;
while(!queue.isEmpty()) {
Vertex tmp = queue.poll();
if(visited[tmp.x]) continue;
visited[tmp.x] = true;
// Sol.2에서 변경되는 부분
for(Edge e: list[tmp.x]) {
go[e.v] = Math.min(go[e.v], tmp.cost+e.w);
if(!visited[e.v]) {
queue.offer(new Vertex(e.v, go[e.v]));
}
}
}
round[i] += go[X];
}- 결과 : 시간 제한, 메모리 제한 안에 들어오긴 하지만 비효율적 (91,732 KB / 732 ms)
Solution 2
다익스트라 계산 시 각 지점의 min 값이 변경될 때만 큐에 삽입함
Sol.1에서 주석 표시된 부분에 조건을 추가함
for(Edge e: list[tmp.x]) {
if(go[e.v]>tmp.cost+e.w) { // 이 조건을 추가함
go[e.v] = tmp.cost+e.w;
if(!visited[e.v])
queue.offer(new Vertex(e.v, go[e.v]));
}
}-
결과 : 이전보다 메모리와 시간이 더 줄어듦 (58,316 KB / 528 ms)
하지만 여전히 최선의 방법이 아닌 것 같음
Solution 3
(2) (각자의 집) → (파티장 X) 를 구할 때 간선의 시작과 끝점을 바꿔서 다른 리스트에 저장
이번엔 dijkstra를 함수로 다음과 같이 분리했다.
static void dijkstra(int[] arr, List<Edge>[] li) {
Arrays.fill(arr, Integer.MAX_VALUE);
queue.offer(new Vertex(X, 0));
arr[X] = 0;
while(!queue.isEmpty()) {
Vertex tmp = queue.poll();
if(visited[tmp.x]) continue;
visited[tmp.x] = true;
for(Edge e: li[tmp.x]) {
arr[e.v] = Math.min(arr[e.v], tmp.cost+e.w);
if(!visited[e.v]) {
queue.offer(new Vertex(e.v, arr[e.v]));
}
}
}
}위의 방법과 다르게 static List<Edge>[] list2; 으로 리스트를 하나 더 사용함
(파티장 X) ↔ (각자의 집)의 왕복 시간 구하기
// X에서 집 가는 길
dijkstra(round, list);
// 각 지점에서 X에 가는 길
for(int b=0; b<visited.length; b++) {
visited[b] = false;
}
dijkstra(go, list2);- 결과 : 효율성이 훨씬 좋아짐 (18,576 KB / 180 ms)
- key : 모든 지점에서 한 지점으로의 비용 구하기 → 간선의 u, v를 바꿔서 계산
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder output = new StringBuilder();
static StringTokenizer tokens;
static int N, M, X, round[], go[], u, v, w, answer;
static List<Edge>[] list;
static List<Edge>[] list2;
static boolean[] visited;
static PriorityQueue<Vertex> queue = new PriorityQueue<>();
static class Edge{
int v;
int w;
public Edge(int v, int w) {
super();
this.v = v;
this.w = w;
}
}
static class Vertex implements Comparable<Vertex>{
int x;
int cost;
public Vertex(int x, int cost) {
super();
this.x = x;
this.cost = cost;
}
@Override
public int compareTo(Vertex o) {
return Integer.compare(this.cost, o.cost);
}
}
static void dijkstra(int[] arr, List<Edge>[] li) {
Arrays.fill(arr, Integer.MAX_VALUE);
queue.offer(new Vertex(X, 0));
arr[X] = 0;
while(!queue.isEmpty()) {
Vertex tmp = queue.poll();
if(visited[tmp.x]) continue;
visited[tmp.x] = true;
for(Edge e: li[tmp.x]) {
arr[e.v] = Math.min(arr[e.v], tmp.cost+e.w);
if(!visited[e.v]) {
queue.offer(new Vertex(e.v, arr[e.v]));
}
}
}
}
public static void main(String[] args) throws IOException {
tokens = new StringTokenizer(input.readLine(), " ");
N = Integer.parseInt(tokens.nextToken());
M = Integer.parseInt(tokens.nextToken());
X = Integer.parseInt(tokens.nextToken());
visited = new boolean[N+1];
go = new int[N+1];
round = new int[N+1];
list = new ArrayList[N+1];
list2 = new ArrayList[N+1];
for(int i=1; i<list.length; i++) {
list[i] = new ArrayList<Edge>();
list2[i] = new ArrayList<Edge>();
}
for(int i=0; i<M; i++) {
tokens = new StringTokenizer(input.readLine(), " ");
u = Integer.parseInt(tokens.nextToken());
v = Integer.parseInt(tokens.nextToken());
w = Integer.parseInt(tokens.nextToken());
list[u].add(new Edge(v, w));
list2[v].add(new Edge(u, w));
}
// X에서 집 가는 길
dijkstra(round, list);
// 각 지점에서 X에 가는 길
for(int b=0; b<visited.length; b++) {
visited[b] = false;
}
dijkstra(go, list2);
for(int i=1; i<round.length; i++) {
if(i==X) continue;
answer = Math.max(answer, round[i]+go[i]);
}
output.append(answer);
System.out.println(output.toString());
}
}
