DFS와 BFS 프로그램 문제
https://www.acmicpc.net/problem/1260
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다
출력
첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
일반적으로
DFS는 모든 경우의 수를 탐색하는 경우 적합하고
BFS는 최단 경로를 찾는 문제에 적합하다고 한다.
위 문제는 인접행렬과 인접리스트 두 가지 방법으로 문제를 풀 수 있다.
- 인접행렬
node와 edge의 정보를 행렬로 표현하는 방법으로, edge와 상관없이 모든 node를 표현해야 하기 때문에 node의 수가 많을수록 메모리 사용량이 늘어난다. - 인접리스트
node와 edge의 정보를 리스트로 표현하는 방법으로, 연결된 것만 표시하므로 인접행렬에 비해 간단하다.
풀이 1. 인접행렬 사용
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N; // 노드의 개수
static int M; // 에지의 개수
static int V; // 탐색 시작 노드 번호
static int[][] arr; // 인접행렬
static boolean[] visit; // 방문여부
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
V = sc.nextInt();
arr = new int[1001][1001]; // 최대로 주어질 수 있는 입력 값 + 1
visit = new boolean[1001]; // 최대로 주어질 수 있는 입력 값 + 1
for(int i = 0 ; i < M; i++){
int x = sc.nextInt();
int y = sc.nextInt();
arr[x][y] = 1;
arr[y][x] = 1;
}
dfs(V);
visit = new boolean[1001]; // 방문여부 초기화
System.out.println();
bfs(V);
}
public static void dfs(int num){
visit[num] = true; // 시작노드 방문
System.out.print(num + " ");
for(int i = 1; i <= N; i++){ // 애초에 1번부터 for문이 도니 작은 번호의 노드부터 탐색하는 것과 일치
if(arr[num][i] == 1 && !visit[i]){
dfs(i);
}
}
}
public static void bfs(int num){
Queue<Integer> queue = new LinkedList<>();
queue.offer(num);
visit[num] = true;
System.out.print(num + " ");
//Queue가 빌 때까지 반복. 방문 정점은 확인, 출력 후 queue에 넣어 순서대로 확인
while(!queue.isEmpty()){
int temp = queue.poll();
for(int i = 1; i <= N; i++){
if(arr[temp][i] == 1 &&!visit[i]){
queue.offer(i);
visit[i] = true;
System.out.print(i+ " ");
}
}
}
}
}
DFS 흐름
시작노드 1
visit[1] = true
출력: 1
if(arr[1][1] == 1 && !visit[1]) -> if문 false
if(arr[1][2] == 1 && !visit[2]) -> if문 true -> dfs(2)
노드 2
visit[2] = true
출력: 1 2
if(arr[2][1] == 1 &&!visit[1]) -> visit[1]은 true
if(arr[2][2] == 1 &&!visit[2]) -> arr[2][2]는 1이 아니고, visit[2]는 true
if(arr[2][3] == 1 &&!visit[3]) -> arr[2][3]은 1이 아니다
if(arr[2][4] == 1 &&!visit[4]) -> true -> dfs(4)
노드 4
visit[4] = true
출력: 1 2 4
if(arr[4][1] == 1 &&!visit[1]) -> visit[1] true
if(arr[4][2] == 1 &&!visit[2]) -> visit[2] true
if(arr[4][3] == 1 &&!visit[3]) -> true
노드 3
visit[3] = true
출력: 1 2 4 3
-> visit의 모든 요소가 true -> dfs 끝
BFS 흐름
시작노드 1
큐 : 1
visit[1] = true
출력: 1
while(!queue.isEmpty()){ -> 큐에 1 있음
temp = 1;
for(int i = 1; i <= N; i++){
if(arr[1][1] == 1 &&!visit[1]) -> arr[1][1]은 1이 아님
if(arr[1][2] == 1 &&!visit[2]) -> true -> 큐: 2, visit[2] = true
출력: 1 2
if(arr[1][3] == 1 &&!visit[3]) -> true -> 큐: 3 2, visit[3] = true
출력: 1 2 3
if(arr[1][4] == 1 &&!visit[4]) -> true -> 큐: 4 3 2, visit[4] = true
출력: 1 2 3 4
}
}
