[프로그래머스] 가장 먼 노드(49189)

1. 문제 풀이 아이디어

• BFS를 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        List<Integer> list[] = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int[] e : edge) {
            list[e[0]].add(e[1]);
            list[e[1]].add(e[0]);
        }
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        queue.add(1);
        int count = 1;
        while (count < n) {
            int size = queue.size();
            answer = 0;
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int j : list[cur]) {
                    if (visited[j]) continue;
                    visited[j] = true;
                    answer++;
                    count++;
                    queue.add(j);
                }
            }
        }
        return answer;
    }
}

3. 정리

• 간선 정보를 리스트 형태로 저장한다.

• BFS를 시작하기 전에 큐(queue)와 방문 여부를 체크할 배열(visited)을 준비한다.

• 시작 노드는 1번으로 설정하고, 이를 큐에 추가한 후 방문 처리한다.

• 큐에서 노드를 하나씩 꺼내며 해당 노드와 연결된 인접 노드를 방문한다.

• 인접 노드를 방문할 때마다 방문 처리를 하고, 큐에 추가한다.

• 탐색 중 answer를 사용하여 가장 멀리 떨어진 노드의 수를 카운트한다.

• BFS 탐색이 끝나면 answer에 저장된 값을 반환하여 가장 멀리 떨어진 노드의 개수를 구한다.