p49189.md

49189. 가장 먼 노드

Summary

🙇‍♂️ URL : https://programmers.co.kr/learn/courses/30/lessons/49189
🤷‍♂️ Difficulty: ?
💆‍♂️ Submissions : Success

Source code

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;

        boolean[][] connect = new boolean[n][n];
        boolean[]   visited = new boolean[n];
        for(int i=0; i<edge.length; i++) {
            for(int j=0; j<edge[i].length; j++) {
                int row = edge[i][0];
                int col = edge[i][1];
                connect[row-1][col-1] = connect[col-1][row-1] = true;
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;

        while(!queue.isEmpty()) {
            int queueSize = queue.size();
            for(int i=0; i<queueSize; i++) {
                int node = queue.poll();
                for(int j=0; j<n; j++) {
                    if(connect[node][j] == true && !visited[j]) {
                        visited[j] = true;
                        queue.offer(j);
                    }
                }
            }
            answer = queueSize;
        }
        return answer;
    }
}

How to Approach

BFS를 이용하였다. 간선 노드에 대한 이차원 행렬을 만들고, 첫 노드부터 시작해서 인접한 노드를 큐로 순환한다. 결국 가장 마지막에 큐에 남는 노드들(?)이 출발지로부터 가장 멀리 떨어져 있는 노드들이다.

그림으로 그려보니 훨씬 이해가 빨랐다. 아무래도 알고리즘 문제는 그림을 먼저 그리면서 문제에 대한 이해도를 높이고, 이를 무슨 방식으로 푸는게 좋은지 생각하는게 중요한 것 같다. 사실 아직도 Queue와 Stack을 어떤 시점에 사용하는 것이 가장 효율적인지에 대해서는 명확하지 않은 것 같다.