📒

[Programmers] 08-1. 가장 먼 노드

상태

완료

수업

Algorithm Solving

주제

Programmers

4 more properties

참고

문제해설

NOTE

school.programmers.co.kr

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

•

입력 값 ⇒ 정수 값(노드 개수), 2차원 정수배열(간선)

•

출력 값 ⇒ 1번 노드로부터 가장 멀리 떨어진 노드가 몇개인가?

문제 로직고민

NOTE

•

다익스트라 알고리즘을 사용해서 1번노드를 기준으로 각 노드의 모든 거리를 구한다!

◦

노드의 개수 2만, 간선의 개수 5만

◦

이차원 배열로 구현하기에는 노드의 개수가 2만이므로 2만 * 2만은 너무 큰값이 나온다.

◦

우선순위 큐를 사용해서 다익스트라를 구현한다.

작성코드

NOTE

import java.util.*;

class Solution {
    class Node{
        private int weight;
        private int source;
        private int dest;
        
        Node(int weight, int source, int dest){
            this.weight = weight;
            this.source = source;
            this.dest = dest;
        }
    }
    
    public int solution(int n, int[][] edge) {
        int v = 0; 

        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        PriorityQueue<Node> pq = new PriorityQueue<Node>((n1,n2) -> Integer.compare(n1.weight, n2.weight));

        for (int[] e : edge) {
            graph.get(e[0] - 1).add(e[1] - 1);
            graph.get(e[1] - 1).add(e[0] - 1);
        }

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[v] = 0;
        pq.add(new Node(0, v, v));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int curr = node.dest;
            if (visited[curr]) continue;
            visited[curr] = true;

            for (int neighbor : graph.get(curr)) {
                if (dist[curr] + 1 < dist[neighbor]) {
                    dist[neighbor] = dist[curr] + 1;
                    pq.add(new Node(dist[neighbor], curr, neighbor));
                }
            }
        }

        int maxDist = Arrays.stream(dist).max().getAsInt();
        return (int) Arrays.stream(dist).filter(d -> d == maxDist).count();
    }
}
Java
복사
다익스트라 공부하면서 작성한 코드

다른사람 풀이

NOTE

import java.util.ArrayList;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] path = new ArrayList[n];
        ArrayList<Integer> bfs = new ArrayList<Integer>();
        int answer = 0;
        int[] dist = new int[n];
        dist[0] = 1;
        int max = 0;

        for(int i = 0; i < edge.length; i++) {
            int num1 = edge[i][0] - 1;
            int num2 = edge[i][1] - 1;
            if(path[num1] == null)
                path[num1] = new ArrayList<Integer>();
            if(path[num2] == null)
                path[num2] = new ArrayList<Integer>();
            path[num1].add(num2);
            path[num2].add(num1);
        }

        bfs.add(0);
        while(!bfs.isEmpty()) {
            int idx = bfs.get(0);
            bfs.remove(0);
            while(!path[idx].isEmpty()) {
                int num = path[idx].get(0);
                path[idx].remove(0);
                bfs.add(num);
                if(dist[num] == 0) {
                    dist[num] = dist[idx] + 1;
                    max = dist[num];
                }
            }
        }


        for(int i = 0; i < n; i++) {
            if(dist[i] == max)
                answer++;
        }

        return answer;
    }
}
Java
복사
가장 평가가 좋은 코드

•

BFS방식으로 풀이를 진행했다. 가중치값이 모두 1이라 가능한 방식