Lv.3 가장 먼 노드

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

프로그래머스

이 문제는 양방향 간선을 가지는 그래프를 생성 후 탐색하는 문제다.

어떤 방법으로 탐색할까 고민했지만 bfs로 생각하는게 마음이 편하다.

dfs로도 탐색이 가능하지만 매우 느리다. (글 마지막에 코드 첨부)

 

거리를 저장하는 배열을 사용할까말까 고민하다가

첫 풀이에서는 배열을 생성하지 않고 ArrayList의 0번 인덱스에 거리를 저장했다.

이때까지는 이게 더 효율적일줄 알았지만..

 

배열을 생성하는 경우와 처리속도가 얼마나 차이나는지 궁금해서

배열을 생성 후 거리를 저장했더니 처리속도가 유의미하게 개선됐다.

 

ArrayList에서 노드를 꺼내와 0번 인덱스를 조회하는 비용이

배열을 생성하는 비용보다 더 크다는 사실에 놀랐다..

인덱스를 조회하는 것은 상수시간(O(1))이 소요되므로

인덱스를 조회하기 위한 노드를 꺼내오는 것

혹은 2번씩 접근해야하는 부분이

무시하지 못할 비용이었던듯 싶다.

 

처리속도가 느리게 나와서 처음엔 잘못 풀었나 싶었지만..

다른 사람의 풀이들을 돌려서 최대 300 ~ 900ms가 소요되는 것을 보면

문제 자체가 평균적으로 소요시간이 긴 문제인 것 같다.

기존 코드

// 기존 코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] nodes = new ArrayList[n + 1];
        
        for (int i = 0; i <= n; i++) {
            nodes[i] = new ArrayList<>();
            nodes[i].add(0);
        }
        for (int[] line : edge) {
            int a = line[0];
            int b = line[1];
            nodes[a].add(b);
            nodes[b].add(a);
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        
        while (!queue.isEmpty()) {
            int now = queue.poll();
            ArrayList<Integer> node = nodes[now];
            for (int i = 1; i < node.size(); i++) {
                int dest = node.get(i);
                ArrayList<Integer> destNode = nodes[dest];
                if (destNode.get(0) == 0 || destNode.get(0) > node.get(0) + 1) {
                    destNode.set(0, node.get(0) + 1);
                    queue.add(dest);
                }
            }
        }
        int max = 0;
        int cnt = 0;
        
        for (int i = 2; i <= n; i++) {
            int distance = nodes[i].get(0);
            if (distance > max) {
                max = distance;
                cnt = 1;
            } else if (distance == max) {
                cnt++;
            }
        }
        
        return cnt;
    }
}

개선 코드

// 개선 코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] nodes = new ArrayList[n + 1]; // N개의 노드를 의미한다. 각 노드는 연결된 노드 목록을 가진다.
        
        for (int i = 0; i <= n; i++) {
            nodes[i] = new ArrayList<>(); // 배열의 각 요소를 ArrayList로 사용하려면 초기화가 필요하다.
        }
        for (int[] line : edge) { // 주어진 간선을 토대로 각 노드를 이어준다.
            int a = line[0];
            int b = line[1];
            nodes[a].add(b); // 양방향 간선이므로
            nodes[b].add(a); // 양쪽에 추가한다.
        }
        int[] distances = new int[n + 1]; // 1번 노드로부터 각 노드까지의 최단거리를 저장하는 배열
        Queue<Integer> queue = new LinkedList<>(); // 큐를 이용하여 너비를 우선으로 탐색한다.
        queue.add(1); // 1번 노드부터 시작하도록 한다.

        while (!queue.isEmpty()) {
            int now = queue.poll(); // 현재 방문한 노드의 번호
            ArrayList<Integer> node = nodes[now]; // 현재 방문한 노드
            for (int dest : node) { // 노드가 담고있는 요소들은 연결된 노드 번호다. 즉, 탐색할 목적지 노드다.
                if (distances[dest] == 0 || distances[dest] > distances[now] + 1) { // 아직 방문하지 않았거나 현재 경로가 최단거리인 경우 true
                    distances[dest] = distances[now] + 1; // 1번 노드로부터 해당 노드까지의 거리를 최단거리로 갱신한다.
                    queue.add(dest); // 탐색할 목록에 추가한다. 최단거리가 갱신됐으므로 이미 방문했어도 다시 확인해야한다.
                }
            }
        }
        int max = 0; // 가장 먼 노드까지의 거리
        int cnt = 0; // 가장 먼 거리를 가진 노드의 개수
        
        for (int i = 2; i <= n; i++) { // 1번 노드는 확인할 필요가 없으니 2번 노드부터 확인한다.
            int distance = distances[i]; // 1번 노드부터 i번 노드까지의 거리 조회
            if (distance > max) { // 현재까지 발견한 가장 먼 노드까지의 거리보다 멀다면 true
                max = distance; // 가장 먼 거리 갱신
                cnt = 1; // 그렇다면 현재 가장 먼 노드는 1개다.
            } else if (distance == max) { // 가장 먼 거리를 가지는 노드를 또 발견한 경우 true
                cnt++; // 가장 먼 노드 수를 증가시킨다.
            }
        }
        
        return cnt; // 가장 먼 노드 수 return;
    }
}

깊이를 우선으로 탐색

// 깊이를 우선으로 탐색
import java.util.ArrayList;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] nodes = new ArrayList[n + 1];
        
        for (int i = 0; i <= n; i++) {
            nodes[i] = new ArrayList<>();
        }
        for (int[] line : edge) {
            int a = line[0];
            int b = line[1];
            nodes[a].add(b);
            nodes[b].add(a);
        }
        int[] distances = new int[n + 1];
        
        dfs(nodes, distances, 1);
        
        int max = 0;
        int cnt = 0;
        
        for (int i = 2; i <= n; i++) {
            int distance = distances[i];
            if (distance > max) {
                max = distance;
                cnt = 1;
            } else if (distance == max) {
                cnt++;
            }
        }
        
        return cnt;
    }
    
    static void dfs(ArrayList<Integer>[] nodes, int[] distances, int now) {
        ArrayList<Integer> node = nodes[now];

        for (int dest : node) {
            if (dest != 1 && distances[dest] == 0 || distances[dest] > distances[now] + 1) {
                distances[dest] = distances[now] + 1;
                dfs(nodes, distances, dest);
            }
        }
        
    }
}