DFS와 BFS를 구현하는 문제입니다.
재귀함수를 통해서 DFS를 구현하고
Queue를 활용해서 BFS를 구현해 주었습니다.
import java.util.*;
import java.io.*;
public class Main {
public static int n;
public static int m;
public static int v;
public static boolean [][] arr;
public static boolean[] visit;
public static void main(String args[]) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a, b;
int num;
Queue<Integer> queue = new LinkedList<>();
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
visit = new boolean[n+1];
arr = new boolean[n+1][n+1];
for(int i=0; i<m; ++i){
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
arr[a][b] = true;
arr[b][a] = true;
}
visit[v] = true;
DFS(v);
System.out.printf("%n");
Arrays.fill(visit, false);
visit[v] = true;
queue.add(v);
while(queue.size() != 0){
num = queue.poll();
System.out.printf("%d ", num);
for(int i=0; i<n+1; ++i){
if(arr[num][i] & !visit[i]){
visit[i] = true;
queue.add(i);
}
}
}
}
public static void DFS(int num){
System.out.printf("%d ", num);
for(int i=0; i<n+1; ++i){
if(arr[num][i] && !visit[i]){
visit[i] = true;
DFS(i);
}
}
}
}
'알고리즘' 카테고리의 다른 글
[Java] 백준 15650번 N과 M (2) (0) | 2023.01.23 |
---|---|
[Java] 백준 15649번 N과 M (1) (0) | 2023.01.23 |
[Java] 백준 10845번 큐 (0) | 2023.01.23 |
[Java] 백준 14891번 톱니바퀴 (1) | 2023.01.20 |
[Java] 백준 14889번 스타트와 링크 (0) | 2023.01.19 |