[lv.3] 가장 먼 노드

https://school.programmers.co.kr/learn/courses/30/lessons/49189#

• 문제
  
  

• 풀이 (bfs)
  0) 가중치가 모두 1인 양방향 그래프, 한 점에서의 가장 먼 노드를 살펴보는 것이기에 다익스트라도 되지만 우선순위 큐가 고장나 여러 버그가 났다.
  1) ArrayList로 이루어진 그래프를 만들어 그 곳에 연결된 인덱스들을 집어넣는다.
  2) BFS를 start에서부터 돌린다.
  3) 노드를 방문하면 방문 처리 후, 연결된 노드들을 방문 여부에 따라 큐에 지금까지의 거리와 함께 집어넣는다.
  4) 이때, 산출된 거리들은 배열에 저장 후 가장 먼 노드를 계산한다.

• 풀이 (다익스트라)
  0) 위와 같이 그래프를 구성한다.
  1) start, 1부터 다익스트라를 돌린다.
  2) 이때, if(dist[next.idx] > dist[now.idx] + next.cost)이면 dist[next.idx] = dist[now.idx] + next.cost인것은 맞으나, 우큐에 인덱스와 함께 현재까지의 start에서부터의 거리를 같이 저장해야 한다.
  즉, queue.add(new Node(next.idx, dist[next.idx]));로, dist를 같이 저장하여 start에서부터 거리가 짧은 노드부터 계산을 해야한다.

• 코드 (bfs)

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public int solution(int n, int[][] edge) {
        int answer = 1;
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<edge.length; i++){
            graph.get(edge[i][0]).add(edge[i][1]);
            graph.get(edge[i][1]).add(edge[i][0]);
        }
        int[] dist = bfs(1, n);
        Arrays.sort(dist);
        int max = dist[dist.length-1];
        for(int i=dist.length-2; i>0; i--){
            if(max == dist[i]) answer++;
            else break;
        }
        return answer;
    }
    public int[] bfs(int start, int n){
        Queue<int[]> queue = new LinkedList<>();
        int[] dist = new int[n+1];
        boolean[] check = new boolean[n+1];
        queue.add(new int[]{start, 0});
        check[start] = true;
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            ArrayList<Integer> nowList = graph.get(now[0]);
            for(int next : nowList){
                if(check[next]) continue;
                check[next] = true;
                dist[next] = now[1]+1;
                queue.add(new int[]{next, now[1]+1});
            }
        }
        return dist;
    }
}

• 코드 (다익스트라)

import java.util.*;

class Node{
    int idx;
    long cost;
    Node(int idx, long cost){
        this.idx = idx;
        this.cost = cost;
    }
}

class Solution {
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    final static long INF = Long.MAX_VALUE/2;
    public int solution(int n, int[][] edge) {
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<edge.length; i++){
            graph.get(edge[i][0]).add(new Node(edge[i][1], 1));
            graph.get(edge[i][1]).add(new Node(edge[i][0], 1));
        }
        long[] dist = dijkstra(1, n);
        long max = Integer.MIN_VALUE;
        for(int i=1; i<dist.length; i++){
            if(dist[i]!=INF)
                max = Math.max(max, dist[i]);
        }
        int answer = 0;
        for(int i=1; i<dist.length; i++){
            if(max == dist[i]) answer++;
        }
        System.out.println(Arrays.toString(dist));
        return answer;
    }
    public long[] dijkstra(int start, int n){
        long[] dist = new long[n+1];
        boolean[] check = new boolean[n+1];
        Arrays.fill(dist, INF);
        PriorityQueue<Node> queue = new PriorityQueue<>(
            (o1, o2) -> Long.compare(o1.cost, o2.cost)
        );
        queue.add(new Node(start, 0));
        dist[start] = 0;
        while(!queue.isEmpty()){
            Node now = queue.poll();
            if(check[now.idx]) continue;
            check[now.idx] = true;
            ArrayList<Node> nowList = graph.get(now.idx);
            for(Node next : nowList){
                if(dist[next.idx] > dist[now.idx] + next.cost){
                    dist[next.idx] = dist[now.idx] + next.cost;
                    queue.add(new Node(next.idx, dist[next.idx]));
                }
            }
        }
        return dist;
    }
}

• 오답 코드 (다익스트라)

import java.util.*;

class Node{
    int idx;
    int cost = 1;
    Node(int idx){
        this.idx = idx;
    }
}

class Solution {
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    final static long INF = Long.MAX_VALUE/2;
    public int solution(int n, int[][] edge) {
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<edge.length; i++){
            graph.get(edge[i][0]).add(new Node(edge[i][1]));
            graph.get(edge[i][1]).add(new Node(edge[i][0]));
        }
        long[] dist = dijkstra(1, n);
        long max = Integer.MIN_VALUE;
        for(int i=1; i<dist.length; i++){
                if(dist[i]!=INF)
            max = Math.max(max, dist[i]);
        }
        int answer = 0;
        for(int i=1; i<dist.length; i++){
            if(max == dist[i]) answer++;
        }
        System.out.println(Arrays.toString(dist));
        return answer;
    }
    public long[] dijkstra(int start, int n){
        long[] dist = new long[n+1];
        boolean[] check = new boolean[n+1];
        Arrays.fill(dist, INF);
        PriorityQueue<Node> queue = new PriorityQueue<>(
            (o1, o2) -> Integer.compare(o1.cost, o2.cost)
        );
        queue.add(new Node(start));
        dist[start] = 0;
        while(!queue.isEmpty()){
            Node now = queue.poll();
            if(check[now.idx]) continue;
            check[now.idx] = true;
            ArrayList<Node> nowList = graph.get(now.idx);
            for(Node next : nowList){
                if(dist[next.idx] > dist[now.idx] + next.cost){
                    dist[next.idx] = dist[now.idx] + next.cost;
                    queue.add(new Node(next.idx));
                }
            }
        }
        return dist;
    }
}