[BOJ_22865] 가장 먼 곳

설명

---

제출 시 계속 틀렸습니다 가 남발해서 다른 사람의 블로그를 참고해서 푼 문제입니다. 해당 문제의 개념은 A,B,C 위치로 부터 각각 가장 가까운 곳으로 부터의 리스트 중 가장 먼 곳을 선택하는 문제입니다. 그래서, 각 A point , 각 B point, 각 C point로 부터 시작하는 위치로 부터의 각 길이를 모두 구하고 이에 대한 길이 중 가장 짧은 길이를 구하고 나서 그들 리스트 중 가장 먼 곳을 가져와서 가장 먼 곳의 위치(인덱스) 값을 리턴해줍니다.

 

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Data implements Comparable<Data>{
        int to;
        int weight;
        public Data(int to, int weight){
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Data o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
    static List<Data>[] graph;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int N = Integer.parseInt(tk.nextToken());
        tk = new StringTokenizer(in.readLine()," ");
        int A = Integer.parseInt(tk.nextToken()) - 1;
        int B = Integer.parseInt(tk.nextToken()) - 1;
        int C = Integer.parseInt(tk.nextToken()) - 1;

        int M = Integer.parseInt(in.readLine());
        graph = new ArrayList[N]; // graph 배열의 크기를 N으로 초기화합니다.
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>(); // graph 배열의 각 원소를 ArrayList로 초기화합니다.
        }
        for (int i = 0; i < M; i++){
            tk = new StringTokenizer(in.readLine()," ");
            int from = Integer.parseInt(tk.nextToken()) - 1;
            int to = Integer.parseInt(tk.nextToken()) - 1;
            int weight = Integer.parseInt(tk.nextToken());
            graph[from].add(new Data(to, weight)); // graph 배열에 연결된 노드와 거리를 추가합니다.
            graph[to].add(new Data(from, weight));
        }
        int[] distA = dijkstra(A, N);
        int[] distB = dijkstra(B, N);
        int[] distC = dijkstra(C, N);
        int max = -1;
        int max_idx = -1;
        for(int i = 0; i < N;i++)
        {
            int a = distA[i];
            int b = distB[i];
            int c = distC[i];
            int min = Math.min(a,b);
            min = Math.min(min,c);
            if(max == min && max_idx >i)
            {
                max_idx = i;
            }
            else if(max < min)
            {
                max = min;
                max_idx = i;
            }

        }
        System.out.println(max_idx + 1);
    }

    private static int[] dijkstra(int start, int N) {
        int [] dist = new int[N];
        boolean[] visited = new boolean[N];
        Queue<Data> q = new PriorityQueue<Data>();
        q.add(new Data(start,0));
        Arrays.fill(dist, 1000_000_000);
        dist[start] = 0;
        while (!q.isEmpty()){
            Data cur = q.poll();
            if(dist[cur.to] < cur.weight) continue;
            visited[cur.to] = true;
            int cnt = 0;
            for (Data data : graph[cur.to]) { 
                int next = data.to;
                int weight = data.weight;
                if(!visited[next]){
                    q.offer(new Data(next, dist[cur.to] + weight));
                    dist[next] = Math.min(dist[next], dist[cur.to] + weight);
                }
            }
        }
        return dist;
    }
}

 

22865번: 가장 먼 곳