728x90
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
풀이
BFS는 큐를 이용하여 동일한 깊이의 단계를 넓게 들어가는것이고, DFS는 깊이 우선으로 갈때까지 가는것이다.
코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public class Main {
static boolean[][] map;
static int n, m;
public static void bfs(int v) {
boolean[] checked = new boolean[n];
Queue<Integer> q = new LinkedList<Integer>();
q.add(v);
checked[v] = true;
while (q.size() > 0) {
int i = q.poll();
System.out.print(i + " ");
for (int j = 1; j < n; j++) {
if (map[i][j] && !checked[j]) {
q.add(j);
checked[j] = true;
}
}
}
}
static boolean[] checked;
public static void dfs(int v) {
if (!checked[v]) {
System.out.print(v + " ");
checked[v]=true;
for (int i = 1; i < n; i++)
if (map[v][i] && !checked[i])
dfs(i);
}
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
n = sc.nextInt() + 1;
m = sc.nextInt();
int v = sc.nextInt();
map = new boolean[n][n];
for (int i = 0; i < m; i++) {
int s = sc.nextInt(), e = sc.nextInt();
map[s][e] = map[e][s] = true;
}
checked = new boolean[n];
dfs(v);
System.out.println();
bfs(v);
}
}
728x90
728x90
'Algorithm > Baekjoon' 카테고리의 다른 글
Baekjoon 11866 요세푸스 문제 0 JAVA (0) | 2022.02.06 |
---|---|
Baekjoon 14500 테트로미노 JAVA (0) | 2022.02.05 |
Baekjoon 1244 스위치 켜고 끄기 JAVA (0) | 2022.02.05 |
Baekjoon 15964 이상한 기호 JAVA (0) | 2022.02.05 |
Baekjoon 1914 하노이 탑 JAVA (0) | 2022.02.05 |
댓글