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

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 그래프 > 가장 먼 노드

 

 

 

 

문제 설명

 

 

 

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

 

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

 

 

 

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

 

 

 

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

 

 

입출력 예 설명

 

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    boolean[] visited;
    ArrayList<Integer>[] graph;
    int answer = 0;
    public int solution(int n, int[][] edge) {
        visited = new boolean[n+1];
        graph = new ArrayList[n+1];
        
        for(int i=1; i<=n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i<edge.length; i++) {
            graph[edge[i][0]].add(edge[i][1]);
            graph[edge[i][1]].add(edge[i][0]);
        }
        
        bfs(1);
        
        return answer;
    }
    
    public void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;
        
        // bfs는 인접한 노드들을 queue에 추가해 주는 방법인데, 바로 queue에 추가하지 않고 tempList에 추가했다가 
        // 한 번에 queue에 추가하기 때문에 같은 거리에 있는 것들의 개수를 셀 수 있었다. => tempList.size()
        while(true) {
            ArrayList<Integer> tempList = new ArrayList<>();
            
            while(!q.isEmpty()) {
                int now = q.poll();

                for(int next : graph[now]) {
                    if(!visited[next]) {
                        visited[next] = true;
                        tempList.add(next);
                    }
                }
            }
            
            if(tempList.size() == 0) return;
            
            answer = tempList.size();
            q.addAll(tempList);
        }
    }
    
}

 

풀이

1. 그래프가 전부 연결되어 있으므로 완전탐색 bfs(너비 우선 탐색) 방법으로 연결된 노드들을 찾아가면 되는데 여기서 해당 depth의 노드들의 개수를 체크하기 위해서 해당 depth의 노드들을 임시 List에 담아놓고 List의 크기를 확인한 뒤 마지막 depth가 아니라면(List의 크기가 0이 아니라면) answer에 업데이트 하고 임시 List에 담아놓은 노드들을 Queue에 담고 다시 탐색을 진행하면 된다.
2. 방문한 노드들을 체크하기 위해 boolean형 배열 visited와 연결된 노드들을 담기 위해서 ArrayList를 원소로 갖는 배열을 생성하고 주어진 edge를 for문을 돌면서 해당 노드에 연결된 노드들을 담는다.
3. 노드 1부터 bfs 탐색을 시작한다.
4. Queue를 생성하고 1을 담은 후에  visited[1]을 true로 한다.
5. 이제 while문을 돌면서 tempList를 생성하고 내부에 Queue가 빌 때까지 반복하는 while문을 하나 더 생성한다.
6. Queue가 빌 때까지 Queue에서 노드를 꺼내 해당 노드와 인접하고 방문하지 않은 노드들을 tempList에 담은 후에 tempList의 크기(해당 depth의 노드 개수)를 answer에 저장하고 Queue에 모두 담아준다.
7. 만약 tempList의 크기가 0이라면 더 이상 먼 거리에 연결된 노드가 없다는 것으로 제일 끝에 있는 노드들이였으므로 종료하고 answer를 반환한다.