[Java] Lv.3 프로그래머스 가장 먼 노드

설명

BFS 코드 짜는 것보다 거리를 어떻게 저장해야 할지 오래 고민한 문제이다.

문제를 보면 1번 노드에서 제일 멀리 떨어진 노드의 개수를 반환하면 되는 문제이다.

시작노드가 1이고 양방향 간선이다. (무방향)

이 문제는 인접행렬로 구현하면 시간 초과가 뜨므로 인접 리스트나 다른 방법으로 구현하자.

나는 인접 리스트로 구현했다.

코드

import java.util.*;
class Solution {
    static List<Integer>[] arr;		// 인접리스트 저장 
    static boolean[] visited;		// 방문 기록 저장 배열
    static int answer;				
    static int[] count;				// 길이 저장 배열
    public int solution(int n, int[][] edge) {
        answer = 0;
        arr = new List[n + 1];	// 노드가 1부터 시작
        visited = new boolean[n + 1];	// 노드가 1부터 시작

		// 리스트 배열 초기화
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }
		// 양방향이므로 서로 추가해준다.
        for (int i = 0; i < edge.length; i++) {
                int s = edge[i][0];
                int e = edge[i][1];
                arr[s].add(e);
                arr[e].add(s);
        }
        count = new int[n + 1];
        
        bfs(1);

        int max = 0;
        // 기록한 거리 배열 중 최대값 찾기
        for (int i = 0; i < count.length; i++) {
            if (count[i] > max) max = count[i];
        }
		
        // 최대값과 같은 거리 배열 개수 answer 에 저장
        for (int i = 0; i < count.length; i++) {
            if (max == count[i]) answer++;
        }
        return answer;
    }
    public static void bfs (int num) {
        Queue<Integer> q = new LinkedList<>();

        q.add(num);
        visited[num] = true;
        while (!q.isEmpty()) {		// 큐에 값이 없을때까지
            int now = q.poll();
            for (int i : arr[now]) {
                if (!visited[i]) {
                    q.add(i);
                    visited[i] = true;
                    count[i] = count[now] + 1;
                }
            }
        }
    }
}