https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 1 복사
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 1 복사
1 2 4 3
1 2 3 4
예제 입력 2 복사
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력 2 복사
3 1 2 5 4
3 1 4 2 5
문제 풀이
- 정점 번호는 1부터 N번까지이다.
- N은 정점의 개수, M은 간선의 개수, V는 탐색을 시작할 정점의 번호
- 입력으로 주어지는 간선은 양방향이다.
☆ BFS 와 DFS 설명
- DFS (Depth-First Search, 깊이 우선 탐색) 알고리즘에 경우 두 가지 방법으로 풀 수 있다.
1) 스택을 이용하는 것이다.
2) 재귀함수를 이용하는 것인데, 재귀 함수의 코드가 훨씬 짧다.
3) 모든 경우의 수를 탐색하고자 하는 미로 문제가 같은 경우에 적합하다. 이유는 미로 문제는 최단 경로가 아닌 탈출하는 경로를 고려해야 하기 때문이다.- BFS (Breadth-First-Search, 너비 우선 탐색) 알고리즘은 Queue를 사용해서 무제를 해결하면 된다.
1) 두 지점 사이의 최단 경로를 찾는 문제에 적합하다.
2) FIFO (First In First Out) 원칙이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
import java.util.*;
import java.io.*;
public class Main {
// 함수에 사용할 변수들
static int N; // 정점 개수
static int M; // 간선 개수
static int k; // 시작 정점
static ArrayList<Integer> arr[];
static boolean[] isVisit;
static StringBuilder sb;
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());
M = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
arr = new ArrayList[N + 1]; // 좌표를 그대로 받아들이기 위해 +1 사용
isVisit = new boolean[N + 1];
sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
arr[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) { // 간선 열결 상태 저장
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[a].add(b);
arr[b].add(a);
}
for (int i = 0; i < arr.length; i++) {
Collections.sort(arr[i]);
}
dfs(k);
isVisit = new boolean[N + 1];
sb.append("\n");
bfs(k);
System.out.println(sb);
}
// 시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출해준다
public static void dfs(int index) {
isVisit[index] = true;
sb.append(index + " "); // 현재 방문한 값 저장
for(int i : arr[index]) { // i의 변수에 현재 방문한 노드에 해당하는 리스트에 담겨있는 값들을 하나씩 할당
if (!isVisit[i]) {
dfs(i); // 다음 방문할 노드 값으로 바꾸어 재귀 함수 실행
}
}
}
public static void bfs(int index) {
isVisit[index] = true;
// 시작점도 Queue에 넣어줘야 한다
Queue<Integer> q = new LinkedList<>();
q.add(index);
// Queue가 empty 될 때까지 반복하고 방문 정점을 확인, 출력 후 Queue에 넣어 순서대로 확인해준다
while(!q.isEmpty()) {
int a = q.poll();
sb.append(a + " ");
for (int i: arr[a]) {
if(!isVisit[i]) {
q.add(i);
isVisit[i] = true;
}
}
}
}
}
|
cs |
|
|
|
'코딩 문제 > 백준 [ Java ]' 카테고리의 다른 글
| [ 백준 2108 / Java ] 통계학 (0) | 2022.01.26 |
|---|---|
| [ 백준 15650 / Java ] N과 M (2) (0) | 2022.01.26 |
| [ 백준 1388 / Java ] 바닥장식 (0) | 2022.01.24 |
| [ 백준 15649 / Java ] N과 M(1) (0) | 2022.01.22 |
| [ 백준 2750 / Java ] 수 정렬하기 (0) | 2022.01.21 |
댓글