Java - [프로그래머스]49189-가장 먼 노드

출처

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

문제

노드의 개수와 간선의 정보가 주어지고, 1번 노드로부터 가장 멀리 떨어진 노드가 몇개인지 구하는 문제입니다.

풀이

출발은 항상 1번이고, 1번으로부터 깊이를 구하는 문제이기 때문에 BFS를 통해 구합니다. 2중 ArrayList를 선언하여 각각의 노드에 대해 연결되어있는 노드의 정보가 담긴 ArrayList를 미리 담아놓고, 방문 여부를 알 수 있는 boolean배열 visited를 인자로 넘겨주어 탐색을 진행합니다.

Queue를 통해 탐색을 진행하는데, 주의할 점은 1층을 기준으로 깊이를 기록해 주어야 한다는 점 입니다. 한 노드와 연결된 모든 노드를 queue에 넣고, depth배열에 depth[next] += depth[x] + 1와 같이 각 노드에 대한 깊이를 기록해줍니다.

마지막으로 depth에 최대값이 몇개 존재하는지 센 후 return하면 됩니다.

코드

import java.util.*;
class Solution {
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public int solution(int n, int[][] edge) {
        for(int i = 0; i < n+1; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int[] x: edge) {
            graph.get(x[0]).add(x[1]);
            graph.get(x[1]).add(x[0]);
        }
        boolean[] visited = new boolean[n+1];
        int answer = bfs(graph, visited, n);
        return answer;
    }
    
    public int bfs(ArrayList<ArrayList<Integer>> graph,
                   boolean[] visited, int n) {
        Queue<Integer> queue = new LinkedList<>();
        int[] depth = new int[n+1];
        queue.add(1);
        visited[1] = true;
        depth[1] = 1;
        while(!queue.isEmpty()) {
            int x = queue.poll();
            for(int i = 0; i < graph.get(x).size(); i++) {
                int next = graph.get(x).get(i);
                if(!visited[next]) {
                    visited[next] = true;
                    depth[next] += depth[x] + 1;
                    queue.add(next);
                }
            }
        }
        int m = Arrays.stream(depth).max().getAsInt();
        int answer = 0;
        for(int x: depth) {
            if(x == m) {
                answer++;
            }
        }
        return answer;
    }
}

실패한 코드

파이썬으로 예전에 푼것처럼 2차원 인접행렬로 그래프를 만들어 풀었습니다. 채점 결과 마지막 문제 2개가 메모리 초과가 나와 실패하였습니다.

노드는 최대 20,000개, 간선은 최대 50,000개에서 최소 1개이다 보니 그 많은 인접행렬을 보는데 많은 시간과 메모리를 잡아먹어 비효율적인 상황이라고 생각하였습니다.

그래서 인접 리스트를 이용하면 노드가 어디로 가야하는지 미리 담아둘 수 있어 불필요한 메모리를 훨씬 단축할 수 있다고 생각되어 다시 풀어보기로 하였습니다.

import java.util.*;
class Solution {
    int[][] graph;
    public int solution(int n, int[][] edge) {
        graph = new int[n+1][n+1];
        for(int[] x: edge) {
            graph[x[0]][x[1]] = 1;
            graph[x[1]][x[0]] = 1;
        }
        boolean[] visited = new boolean[n+1];
        int answer = bfs(graph, visited, n);
        return answer;
    }
    
    public int bfs(int[][] graph,
                   boolean[] visited, int n) {
        Queue<Integer> queue = new LinkedList<>();
        int[] depth = new int[n+1];
        queue.add(1);
        visited[1] = true;
        depth[1] = 1;
        while(!queue.isEmpty()) {
            int x = queue.poll();
            for(int i = 0; i <= n; i++) {
                if(graph[x][i] != 0 && !visited[i]) {
                    queue.add(i);
                    depth[i]+=depth[x] + 1;
                    visited[i] = true;
                }
            }
        }
        int m = Arrays.stream(depth).max().getAsInt();
        int answer = 0;
        for(int x: depth) {
            if(x == m) {
                answer++;
            }
        }
        return answer;
    }
}