バックアップ-1260:DFSとBFS[java]
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static List<Integer>[] adjList; // 인접행렬(가중치 없음)
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 정점의 개수
int M = Integer.parseInt(st.nextToken()); // 간선의 개수
int V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점의 번호
// 각 정점마다 리스트 만들기
adjList = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
adjList[i] = new ArrayList<Integer>();
}
// 문제에서 양방향이라고 함
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
adjList[from].add(to);
adjList[to].add(from);
}
boolean[] visited = new boolean[N+1];
dfs(V, visited);
sb.append("\n");
bfs(V);
System.out.println(sb);
br.close();
}
private static void dfs(int curr, boolean[] visited) {
visited[curr] = true;
sb.append(curr).append(" ");
// 정점 번호가 작은 거부터 방문하도록
Collections.sort(adjList[curr]);
for (int next : adjList[curr]) {
if(!visited[next]) {
dfs(next, visited);
}
}
}
private static void bfs(int n) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[N+1];
queue.offer(n);
visited[n] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
sb.append(curr).append(" ");
// 정점 번호가 작은 거부터 방문하도록
Collections.sort(adjList[curr]);
for (int next : adjList[curr]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}
}
Reference
この問題について(バックアップ-1260:DFSとBFS[java]), 我々は、より多くの情報をここで見つけました https://velog.io/@heoeunah/백준-1260-DFS와-BFS-자바テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol