[BOJ] 1238 파티 - JAVA

1. 문제

1238번: 파티

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

---

2. 풀이

두 번의 다익스트라를 이용한다.

(1) 각자의 마을 -> X번 마을 : 입력받은 도로 순방향을 이용한다.

(2) X번 마을 -> 각자의 마을  : 입력받은 도로 역방향을 이용하면 출발지를 X로 지정하고 풀이할 수 있다.

 

노드 클래스

노드 배열로 첫번째 요소를 관리할 예정이므로 출발지는 저장하지 않고 도착지, 걸리는 시간만 저장한다.

다음 노드의 주소도 저장한다.

private static class Node {
   int to, time;
   Node next;
   Node(int to, int time, Node next){
      this.to = to;
      this.time = time;
      this.next = next;
   }
}

 

static 변수

문제에서 입력받은 N, X를 전역변수로 설정했다.

 

 

다익스트라 메서드

도로 정보가 담긴 Node[]를 받아서 X마을부터 각 마을까지 걸리는 최소시간 반환 메서드다.

 

PriorityQueue를 이용한 다익스트라 기본적인 풀이다. pq의 정렬은 걸린 시간의 오름차순으로 한다.

dist에 충분히 큰 값을 채우고, pq가 빌 때까지 탐색한다.

만약 이미 방문한 마을이라면 다시 방문하지 않는다.

 

Node[현재마을]에는 다음 마을로 갈 수 있는 도로정보가 있다.

만약 dist[다음마을(=road.to)]이 '현재 도로를 이용해 다음 마을로 걸리는 시간(=road.time)' + 현재 도로까지 걸린 시간(now[1]=dist[now[0]]) 보다 같거나 작다면 다시 탐색할 필요가 없다.

dist[road.to]를 갱신하고 pq에 새로운 정보를 추가한다.

 

마지막에 dist를 반환한다.

private static int[] dijkstra(Node[] roads){
   int INF = 100_001;//1000개 마을 x 시간 최대 100 + 1
   int[] dist = new int[N+1];
   boolean[] visited = new boolean[N+1];
   Arrays.fill(dist, INF);

   PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
   pq.offer(new int[]{X,0});
   dist[X] = 0;

   int[] now;
   while(!pq.isEmpty()){
      now = pq.poll();
      if(visited[now[0]]) continue;
      visited[now[0]] = true;
      dist[now[0]] = now[1];

      for(Node road=roads[now[0]];road != null;road = road.next){
         if(dist[road.to] <= road.time+now[1]) continue;
         dist[road.to] = road.time + now[1];
         pq.offer(new int[]{road.to, dist[road.to]});
      }
   }

   return dist;
}

 

 

Main

입력

1.  순방향은 forward, 역방향은 reverse Node배열에 저장한다. 배열 크기는 N+1이다. (마을 수가 1부터 시작)

2.  도로가 입력될 때마다 forward, reverse에 추가한다. 새로운 노드를 생성해 저장하면서 그 노드의 next주소로 현재의 forward[from](reverse[to])을 설정하면 된다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());//마을 수
int M = Integer.parseInt(st.nextToken());//도로 수
X = Integer.parseInt(st.nextToken());//목적지

Node[] forward = new Node[N+1];
Node[] reverse = new Node[N+1];

int from, to, time;
for(int i=0;i<M;i++){
   st = new StringTokenizer(in.readLine());
   from = Integer.parseInt(st.nextToken());
   to = Integer.parseInt(st.nextToken());
   time = Integer.parseInt(st.nextToken());

   forward[from] = new Node(to, time, forward[from]);
   reverse[to] = new Node(from, time, reverse[to]);
}

 

출력

1.  dijkstra 메서드를 두 번 실행해서 그 결과를 각각 f, r에 저장한다.

2.  f,r 두 요소를 합친 값을 하나씩 비교해가면서 가장 큰 값을 알아낸다. (이때 X번째는 제외한다)

3.  출력한다.

int[] f = dijkstra(forward);
int[] r = dijkstra(reverse);

int max=0;
for(int i=1;i<=N;i++){
   if(i==X) continue;
   if(f[i] + r[i] < max) continue;
   max = f[i] + r[i];
}

System.out.println(max);

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_1238_파티2 {
   static int N, X;

   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());//마을 수
      int M = Integer.parseInt(st.nextToken());//도로 수
      X = Integer.parseInt(st.nextToken());//목적지

      Node[] forward = new Node[N + 1];
      Node[] reverse = new Node[N + 1];

      int from, to, time;
      for (int i = 0; i < M; i++) {
         st = new StringTokenizer(in.readLine());
         from = Integer.parseInt(st.nextToken());
         to = Integer.parseInt(st.nextToken());
         time = Integer.parseInt(st.nextToken());

         forward[from] = new Node(to, time, forward[from]);
         reverse[to] = new Node(from, time, reverse[to]);
      }

      int[] f = dijkstra(forward);
      int[] r = dijkstra(reverse);

      int max = 0;
      for (int i = 1; i <= N; i++) {
         if (i == X) continue;
         if (f[i] + r[i] < max) continue;
         max = f[i] + r[i];
      }

      System.out.println(max);
   }

   private static int[] dijkstra(Node[] roads) {
      int INF = 100_001;//1000개 마을 x 시간 최대 100 + 1
      int[] dist = new int[N + 1];
      boolean[] visited = new boolean[N + 1];
      Arrays.fill(dist, INF);

      PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
      pq.offer(new int[]{X, 0});
      dist[X] = 0;

      int[] now;
      while (!pq.isEmpty()) {
         now = pq.poll();
         if (visited[now[0]]) continue;
         visited[now[0]] = true;
         dist[now[0]] = now[1];

         for (Node road = roads[now[0]]; road != null; road = road.next) {
            if (dist[road.to] <= road.time + now[1]) continue;
            dist[road.to] = road.time + now[1];
            pq.offer(new int[]{road.to, dist[road.to]});
         }
      }

      return dist;
   }

   private static class Node {
      int to, time;
      Node next;

      Node(int to, int time, Node next) {
         this.to = to;
         this.time = time;
         this.next = next;
      }
   }
}

---

3. 결과

처음에는 Node클래스를 사용하지 않고 Map<Integer, ArrayList<int[]>>를 이용했다. 아무래도 몇 번 더 객체 생성을 해야 하니 좀 더 오래 걸린 것 같다.