[規格1260]BFSとDFS Java
19360 ワード
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ1260 {
static int N, M, V;
static boolean[] visited;
static boolean[][] adjMatrix;
static StringBuilder sb;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
adjMatrix = new boolean[N + 1][N + 1];
visited = new boolean[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine(), " ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
adjMatrix[from][to] = adjMatrix[to][from] = true;
}
dfs(V);
sb.append("\n");
bfs();
out.write(sb.toString());
out.close();
in.close();
}
private static void dfs(int V) {
visited[V] = true;
sb.append(V).append(" ");
for(int i = 0; i < N+1; i++) {
if(adjMatrix[V][i] && !visited[i]) {
dfs(i);
}
}
}
private static void bfs() {
Queue<Integer> queue = new LinkedList<Integer>();
boolean[] visited = new boolean[N+1];
queue.offer(V);
visited[V] = true;
while(!queue.isEmpty()) {
int current = queue.poll();
sb.append(current).append(" ");
for(int i = 1; i < N+1; i++) {
if(adjMatrix[current][i] && !visited[i]) {
queue.offer(i);
visited[i] = true;
}
}
}
}
}
Reference
この問題について([規格1260]BFSとDFS Java), 我々は、より多くの情報をここで見つけました https://velog.io/@yoonjy1106/백준-1260-BFS와-DFS-자바Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol