プログラマ-最も遠いノード[java]


質問元:https://programmers.co.kr/learn/courses/30/lessons/49189

問題の説明


n個のノードを含むグラフィック.各ノード番号は1からnです.1ノードに最も近いノード数を取得します.最遠ノードとは、最短経路に移動したときに幹線数が最も多いノードを指す.
ノード個数n、幹線情報を含む2次元配列頂点をパラメータとして指定する場合は、1番ノードに最も近いノード数を返す解関数を作成します.
せいげんじょうけん

  • ノード数nは2万個を超えない.

  • 幹線は双方向で、全部で1本以上50000本以下の幹線があります.

  • 頂点配列の各行[a,b]は、a番ノードとb番ノードの間に幹線があることを示す.
  • 入力例
    n = 6, vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
    サンプル出力
    3
    I/O例説明
    下図に示すように,1番ノードから最も遠いノードは4,5,6番ノードである.

    問題を解く

    import java.util.*;
    
    class Solution {
        public int solution(int n, int[][] edge) {
            
            int answer = 0;
            Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
            
            for(int i = 0; i < edge.length; i++) {
                
                ArrayList<Integer> nodes = graph.containsKey(edge[i][0]) ? 
                    graph.get(edge[i][0]) : new ArrayList<Integer>();
                nodes.add(edge[i][1]);
                graph.put(edge[i][0], nodes);
                
                nodes = graph.containsKey(edge[i][1]) ? 
                    graph.get(edge[i][1]) : new ArrayList<Integer>();
                nodes.add(edge[i][0]);
                graph.put(edge[i][1], nodes);
            }
    
            return bfs(graph, 1);
        }
        
        public static int bfs(Map<Integer, ArrayList<Integer>> graph, int n) {
            
            Queue<Integer> next = new LinkedList<>();
            Set<Integer> visited = new HashSet<>();
            
            next.add(n);
            visited.add(n);
            
            int answer = 0;
            int count = next.size();
            
            while(!next.isEmpty()) {
                
                if(count == 0) {
                    count = next.size();
                    answer = next.size();
                }
                
                int current = next.poll();
                ArrayList<Integer> nextNodes = graph.get(current);
                
                for(int node : nextNodes) {
                    if(!visited.contains(node)) {
                        visited.add(node);
                        next.add(node);
                    }
                }
                count--;
            }
            
            return answer;
        }
    }
    BFS方式で問題を解く.
    白駿-トマト問題と同様に解き、まずグラフをハッシュ図に、ノード1から隣接ノードがアクセスしていないノードであればキューに入れ、1段階ごとにキューサイズを記憶するように解きます.
    上図の画像の例
    Node 1--->隣接ノードの保存[2,3]--->2
    Node 2,3--->隣接ノードの保存[5,4,6]--->3
    Node 5,4,6---->隣接ノードなし[](すべてアクセス済み)--->0--->前のフェーズで保存した3を返します.