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

[프로그래머스] L3 가장 먼 노드

[풀이]

연길리스트를 이용한 그래프 표현

[ 메모리 ]

 

n의 크기가 2만이기 때문에 인접 행렬로 표현한다면

20000 X 20000 = 400000000 = 약 400MB가 될 것이다.

(int[1000][1000] = 1000x1000x4byte = 4MB)

 

[ 시간 ] 

 

인접행렬을 사용할 경우 연결된 노드를 확인하는 과정에서 이중 for문을 사용해야 한다.

이때 20000 x 20000 = 400000000 = 4억 = 약 4초가 걸린다

for(int from=0; from<20000; from++){
	for(int to = 0; to < 20000; to++){
    }
}

 

따라서 해당 문제는 인접 리스트로 해결한다.

현재 노드와 거리를 큐에 넣어 큐에 원소가 없을 때까지 반복문을 돌린다. 

-끝-

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        List<ArrayList<Integer>> list = new ArrayList<>();
        for(int i=0; i<=n; i++)
            list.add(new ArrayList<Integer>());
        for(int i=0; i<edge.length; i++){
            list.get(edge[i][0]).add(edge[i][1]); // 0 -> 1
            list.get(edge[i][1]).add(edge[i][0]); // 1 -> 0 양방향 
        } // 노드의 개수가 최대 20000개, 메모리를 고려해서 인접행렬보다는 인접리스트를 사용한다
 
        boolean[] visit = new boolean[20001]; // 방문한 노드 번호
        int ans = 0; // 결과
        int max = 0; // 최대 거리
        
        Queue<int[]> q = new LinkedList<int[]>(); // from좌표, cnt
        q.add(new int[] {1,1});
        visit[1] = true;
        while(!q.isEmpty()){
            int[] temp = q.poll();
            int from = temp[0];
            int cnt = temp[1];
            if(max==cnt){ // 기존과 동일하게 떨어진 경우
                ans++;
            }else if(max<cnt){ // 가장 멀리 떨어진 경우
                max = cnt;
                ans = 1;
            }
            ArrayList<Integer> toList = list.get(from);
            for(int i = 0; i<toList.size(); i++){
                int to = toList.get(i);
                if(!visit[to]){
                    visit[to] = true;
                    q.add(new int[] {to, cnt+1});
                }
            }
        }
        return ans;
    }
}