プログラマ-最も遠いノード[java]
14987 ワード
質問元: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番ノードである.
白駿-トマト問題と同様に解き、まずグラフをハッシュ図に、ノード1から隣接ノードがアクセスしていないノードであればキューに入れ、1段階ごとにキューサイズを記憶するように解きます.
上図の画像の例
Node 1--->隣接ノードの保存[2,3]--->2
Node 2,3--->隣接ノードの保存[5,4,6]--->3
Node 5,4,6---->隣接ノードなし[](すべてアクセス済み)--->0--->前のフェーズで保存した3を返します.
問題の説明
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を返します.
Reference
この問題について(プログラマ-最も遠いノード[java]), 我々は、より多くの情報をここで見つけました https://velog.io/@davidko/프로그래머스-가장-먼-노드javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol