파티 (BJ_G3_1238)

1. 문제 링크

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

1238번: 파티

---

 

2. 나의 코드

메모리: 45908kb
시간: 592ms
코드 길이: 2320B
시간 복잡도 :  O((V + E)logV)
설명
- 다익스트라 알고리즘 사용

package com.problem.BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_1238 {
	static class Node implements Comparable<Node> {
		int v, weight;

		public Node(int v, int weight) {
			this.v = v;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	static int N, M, X;	// 정점의 갯수, 간선의 갯수, 파티 장소
	static int[] dist;
	static boolean[] visited;
	static int[] result;
	static ArrayList<ArrayList<Node>> graph;
	
	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());
		dist = new int[N + 1];
		visited = new boolean[N + 1];
		result = new int[N + 1];
		graph = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			graph.get(from).add(new Node(to, weight));
		}
		for (int i = 1; i <= N; i++) {
			Arrays.fill(dist, Integer.MAX_VALUE);
			Arrays.fill(visited, false);
			dijkstra(i);
			if (i == X) {
				for (int j = 1; j <= N; j++) {
					if (j == X) continue;
					result[j] += dist[j];
				}
			} else {
				result[i] += dist[X];
			}
		}
		int max = 0;
		for (int n : result) {
			if (max < n) max = n;
		}
		System.out.println(max);
	}

	public static void dijkstra(int s) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		dist[s] = 0;
		pq.add(new Node(s, 0));
		
		while (!pq.isEmpty()) {
			Node now = pq.poll();
			
			if (!visited[now.v]) visited[now.v] = true;
			
			if (now.v == X && s != X) break;
			
			for (Node next : graph.get(now.v)) {
				if (!visited[next.v] && now.weight + next.weight < dist[next.v]) {
					dist[next.v] = now.weight + next.weight;
					pq.add(new Node(next.v, dist[next.v]));
				}
			}
		}
	}
}

 

---

 

3. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Town implements Comparable<Town> {
    int end;
    int weight;
 
    Town(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Town arg0) {
        return weight - arg0.weight;
    }
}
 
public class Main {
    static final int INF = 987654321;
    static ArrayList<ArrayList<Town>> arrList, reverse_arrList;
    static int N, X;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
 
        arrList = new ArrayList<>(); // 문제의 입력을 그대로 받은 배열
        reverse_arrList = new ArrayList<>(); // 문제의 입력을 반대로 받은 배열
 
        for (int i = 0; i <= N; i++) {
            arrList.add(new ArrayList<>());
            reverse_arrList.add(new ArrayList<>());
        }
 
        // arrList와 reverse_arrList를 각각 단방향 인접리스트로 구현
        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());
 
            arrList.get(start).add(new Town(end, weight));
            reverse_arrList.get(end).add(new Town(start, weight));
        }
 
        int[] dist1 = dijkstra(arrList); // X에서 시작점들 사이의 최단거리
        int[] dist2 = dijkstra(reverse_arrList); // 시작점들에서 X 사이의 최단거리
 
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dist1[i] + dist2[i]);
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 다익스트라 알고리즘
    public static int[] dijkstra(ArrayList<ArrayList<Town>> a) {
        PriorityQueue<Town> pq = new PriorityQueue<>();
        pq.offer(new Town(X, 0));
        
        boolean[] check = new boolean[N + 1];
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);
        dist[X] = 0;
 
        while (!pq.isEmpty()) {
            Town curTown = pq.poll();
            int cur = curTown.end;
 
            if (!check[cur]) {
                check[cur] = true;
 
                for (Town town : a.get(cur)) {
                    if (!check[town.end] && dist[town.end] > dist[cur] + town.weight) {
                        dist[town.end] = dist[cur] + town.weight;
                        pq.add(new Town(town.end, dist[town.end]));
                    }
                }
            }
        }
        return dist;
    }
 
}

 

---

 

4. 배운 점

- 다익스트라는 암기다. 외우자