[BOJ] 파티

[1238] 파티

https://www.acmicpc.net/problem/1238

• N개의 숫자로 구분된 마을에는 한 명의 학생이 살고 있음, 마을 = 정점 V
• 이 마을에는 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti의 시간을 소비한다. 도로 = 가중치가 있는 간선 E
• N명의 학생이 X(1<=X<=N)번 마을에 모여서 파티를 벌이기로했다.
• 각각의 학생들은 파티에 참석하기 위해 X번 마을까지 걸어가서 다시 각자의 마을로 돌아와야한다. = 왕복 이동
• 이 도로들은 단뱡향이기 때문에 그들이 오고 가는 길이 다를지도 모른다.
• N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

 

Solution 1

• 처음에 풀이했던 방식은 (1) N번 마을에서 X까지 가는 비용 + (2) X 마을에서 N번의 마을로 돌아가는 비용]을 계산해서 답을 구하는 방식으로 풀었었는데
• 이 풀이 방식의 문제점은 (1) 과정에서 각 마을을 출발점으로 하여 X에 도착하는 비용을 구했기 때문에 dijkstra(N)를 N번 계산해야 했다. + (2) 에서는 dijkstra(X) 한 번만 계산
• X에 대한 최단 경로만 구하면 되는 상황에서 모든 정점에 대해 dijkstra 연산을 하는 것은 비효율적인 방식이다.

 

 

소스코드 1

 

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 int V,E,X;
    static List<List<Node>> graph;
    static int[] distance, go, back;
    static boolean[] visited;
    
    static class Node implements Comparable<Node>{
        private int idx;
        private int weight;
        
        public Node(int idx, int weight) {
            this.idx = idx;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = stoi(st.nextToken());
        E = stoi(st.nextToken());
        X = stoi(st.nextToken());
        
        init();
        int u,v,w;
        for(int i = 0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            u = stoi(st.nextToken());
            v = stoi(st.nextToken());
            w = stoi(st.nextToken());
            
            graph.get(u).add(new Node(v,w));
        }
        
        for(int i = 1; i<=V; i++) {
            Arrays.fill(visited, false);
            go[i] = dijkstra(i);
        }
        int max = Integer.MIN_VALUE;
        int answer = 0;
        for(int i = 1; i<=V; i++) {
            if(max < go[i] + back[i]) {
                max = go[i] + back[i];
            }
        }
        System.out.println(max);
    }
 
    static int dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Arrays.fill(distance, Integer.MAX_VALUE);
        
        distance[start] = 0;
        pq.add(new Node(start, 0));
        
        while(!pq.isEmpty()) {
            int cur = pq.poll().idx;
            
            if(visited[cur]) continue;
            visited[cur] = true;
            
            for(Node node : graph.get(cur)) {
                if(distance[node.idx] > distance[cur] + node.weight) {
                    distance[node.idx] = distance[cur] + node.weight;
                    pq.add(new Node(node.idx, distance[node.idx]));
                }
            }
        }
        
        if(start == X) {
            back = distance.clone();
        }
        return distance[X];
    }
    
    
    static void init() {
        graph = new ArrayList<List<Node>>();
        distance = new int[V+1];
        go = new int[V+1];
        back = new int[V+1];
        visited = new boolean[V+1];
        for(int i = 0; i<=V; i++) {
            graph.add(new ArrayList<>());
        }
    }
 
    static int stoi(String s) {
        return Integer.valueOf(s);
    }
}

 

 

Solution 2

• Solution 1 을 개선한 풀이 방식
• 인접 리스트(graph2)를 하나 더 만든 뒤, 입력 받은 간선 정보를 반대로 뒤집어 저장하여 X를 출발점으로 한 번 더 dijkstra 연산을 수행했다.
• 한 번의 연산으로 N개의 마을에서 X 마을에 도착하는 비용을 구할 수 있었다.

 

소스코드 2

 

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 int V, E, X;
    static List<List<Node>> graph1, graph2;
    static int[] distance, go, back;
    static boolean[] visited;
 
    static class Node implements Comparable<Node> {
        private int idx;
        private int weight;
 
        public Node(int idx, int weight) {
            this.idx = idx;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = stoi(st.nextToken());
        E = stoi(st.nextToken());
        X = stoi(st.nextToken());
 
        init();
        int u, v, w;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            u = stoi(st.nextToken());
            v = stoi(st.nextToken());
            w = stoi(st.nextToken());
 
            graph1.get(u).add(new Node(v, w));
            graph2.get(v).add(new Node(u, w));
        }
 
        dijkstra(X, go, graph2);
        Arrays.fill(visited, false);
        dijkstra(X, back, graph1);
        int max = Integer.MIN_VALUE;
        int answer = 0;
        for (int i = 1; i <= V; i++) {
            if (max < go[i] + back[i]) {
                max = go[i] + back[i];
            }
        }
        System.out.println(max);
    }
 
    static int[] dijkstra(int start, int[] distance, List<List<Node>> graph) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Arrays.fill(distance, Integer.MAX_VALUE);
 
        distance[start] = 0;
        pq.add(new Node(start, 0));
 
        while (!pq.isEmpty()) {
            int cur = pq.poll().idx;
 
            if (visited[cur])
                continue;
            visited[cur] = true;
 
            for (Node node : graph.get(cur)) {
                if (distance[node.idx] > distance[cur] + node.weight) {
                    distance[node.idx] = distance[cur] + node.weight;
                    pq.add(new Node(node.idx, distance[node.idx]));
                }
            }
        }
 
        return distance;
    }
 
    static void init() {
        graph1 = new ArrayList<List<Node>>();
        graph2 = new ArrayList<List<Node>>();
        distance = new int[V + 1];
        go = new int[V + 1];
        back = new int[V + 1];
        visited = new boolean[V + 1];
        for (int i = 0; i <= V; i++) {
            graph1.add(new ArrayList<>());
            graph2.add(new ArrayList<>());
        }
    }
 
    static int stoi(String s) {
        return Integer.valueOf(s);
    }
}