프로그래머스 가장 먼 노드 Java

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

프로그래머스

1. 문제 설명

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번 노드입니다.

 

2. 시나리오

• Map을 사용해서 양방향 그래프를 표현한다.
• 방문 표시할 배열과 거리마다 노드의 개수를 표시할 배열(count)이 필요하다.
  • 거리의 최대 개수는 (노드의 개수 - 1)이다.
• 그래프를 탐색하면서 각 노드의 거리를 구해야하기 때문에 BFS를 사용한다.
• BFS로 1번 노드부터 방문하지 않은 연결된 노드를 탐색하면서,
  큐에서 뽑은 노드의 거리를 count[노드의 거리]에 1씩 더해준다.
• 모든 노드를 탐색 후, count 배열을 뒤부터 체크하며, 값이 0이 아닐 때 인덱스를 반환하여 최대 거리를 찾는다.
• 최대 거리의 노드의 개수를 반환한다.

 

3. 코드

import java.util.*;

class Solution {
    
    static Map<Integer, ArrayList<Integer>> map = new HashMap<>();
    static boolean[] visited;
    static int[] count;
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        input(n, edge);
        bfs();
        return getMax();
        
    }
    
    public int getMax() { // count 배열을 뒤부터 돌면서 최대 거리를 찾는다.
        for (int i = count.length - 1; i >= 0; i--) {
            if (count[i] != 0)
                return count[i];
        }
        
        return 0;
    }
    
    public void bfs() {
        Deque<Node> queue = new ArrayDeque<>();
        
        queue.add(new Node(1, 0));
        visited[1] = true;
        
        while (!queue.isEmpty()) {
            
            Node poll = queue.pollFirst();
            count[poll.w]++; //count[노드의 거리]에 1씩 더해준다.
            
            ArrayList<Integer> list = map.get(poll.n);
            
            for(int i = 0 ; i < list.size(); i++) {
                int linked = list.get(i);
                if (!visited[linked]) {
                    queue.add(new Node(linked, poll.w + 1));
                    visited[linked] = true;
                }
            }
        }
    }
    
    
    public void input(int n, int[][] arr) { //그래프를 Map으로 표현한다.
        
        visited = new boolean[n + 1];
        count = new int[n + 1]; //노드의 거리의 최대값은 (노드의 개수 - 1)
        
        for (int i = 1; i <= n; i++) {
            map.put(i, new ArrayList<>());
        }
        
        for (int i = 0 ; i < arr.length; i++) {
            int a = arr[i][0];
            int b = arr[i][1];
            
            map.get(a).add(b);
            map.get(b).add(a);
        }
    }
    
    class Node { //n은 노드의 번호, w는 거리
        int n, w;
        
        public Node (int n, int w) {
            this.n = n;
            this.w = w;
        }
    }
}