[백준 1238] 파티(JAVA)

백준 1238번 문제 - 파티

1238번: 파티

---

문제 분석 

 

 

• N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
• N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다.
• 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
• 이 때,  학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
• N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

---

해결 포인트

•  
• 다익스트라(Dijkstra) 알고리즘 사용
• Edge 클래스 구현
  • 도착지 end
  • 가중치 w
•  결과를 저장할 results 배열 구현
• Edge Comparable는 가중치가 작은 순으로 정렬되도록 구현
• 우선순위 큐 사용
  •  Queue<Edge> q = new PriorityQueue<>(); 
• 방문 확인 visited 배열 구현
• 처음 시작 위치 큐에 삽입 
  •  q.add(new Edge(start, 0)); 
•  큐가 빌 때까지 반복
  • 큐에서 하나 꺼내기
  • 방문한 위치면 패스(continue)
  • 방문 안한 위치면 방문 등록 후, 갈 수 있는 공간 큐에 추가

---

코드

 

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

public class Main {
    public static int [][] result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        ArrayList<Edge> [] edges = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            edges[i] = new ArrayList<>();
        }

        result = new int[N+1][N+1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            edges[a].add(new Edge(b,w));
            result[a][b] = w;
        }

        for (int i = 1; i <= N; i++) {
            BFS(i, edges);
        }

        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(result[i][X] + result[X][i], max);
        }
        bw.write(max+"\n");
        bw.flush();

        br.close();
        bw.close();
    }

    public static void BFS(int start, ArrayList<Edge> [] edges) {
        Queue<Edge> queue = new PriorityQueue<>();
        boolean[] visited = new boolean[edges.length];

        queue.add(new Edge(start, 0));

        while (!queue.isEmpty()) {
            Edge value = queue.poll();

            if(!visited[value.end]) {
                visited[value.end] = true;
                for (Edge e : edges[value.end]) {
                    if (!visited[e.end]) {
                        if(result[start][e.end] != 0)
                            result[start][e.end] = Math.min(value.w + e.w, result[start][e.end]);
                        if(result[start][e.end] == 0)
                            result[start][e.end] = value.w + e.w;

                        queue.add(new Edge(e.end, value.w + e.w));
                    }
                }
            }
        }
    }

    public static class Edge implements Comparable<Edge> {
        int end;
        int w;
        public Edge(int end, int w) {
            this.end = end;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            if(w == o.w)
                return end - o.end;
            return w - o.w;
        }
    }
}