보라코딩
백준 자바 :: DFS와 BFS 본문

import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] list; // 리스트의 배열
static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
list = new ArrayList[N+1];
for (int i = 1; i <= N; i++){
list[i] = new ArrayList<Integer>();
}
for (int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
list[first].add(end);
list[end].add(first);
}
// 주의 sort (번호 작은 것부터)
for(int i = 1; i <= N; i++){
Collections.sort(list[i]);
}
visited = new boolean[N+1];
DFS(start);
System.out.println();
visited = new boolean[N+1];
BFS(start);
}
static void DFS(int node){
System.out.print(node + " ");
visited[node] = true;
for(int num : list[node]){
if(!visited[num]){
DFS(num);
}
}
}
static void BFS(int node){
Queue<Integer> q = new LinkedList<>();
q.offer(node);
visited[node] = true;
while(!q.isEmpty()){
int nowNode = q.poll();
System.out.print(nowNode + " ");
for(int num : list[nowNode]){
if(!visited[num]){
visited[num] = true;
q.add(num);
}
}
}
}
}
'백준(java)' 카테고리의 다른 글
백준 자바 :: 단지번호붙이기(DFS) / 유기농배추(DFS) / 섬의개수(DFS) (0) | 2024.07.19 |
---|---|
백준 자바 :: 바이러스 (0) | 2024.07.17 |
백준 자바 :: 신기한 소수 (DFS) (0) | 2024.07.02 |
백준 자바 :: 연결요소의 개수 (0) | 2024.07.01 |
백준 문제집 (0) | 2024.04.08 |