728x90
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부터 방문된 점을 순서대로 출력하면 된다.
풀이 방법
DFS : 깊이 우선 탐색 (스택, 혹은 재귀함수)
- 방문여부 검사 & 반복문을 통해 원하는 조건 탐색
BFS : 너비 우선 탐색 (큐)
- 방문여부 검사 & 큐에 값을 삽입, while문을 통한 전체의 조건과 값을 추출 & 반복문
작성 코드
|
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
|
package baekjoon.graphTraversal;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ_1260 {
static int N,M,V;
static int arr[][];
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());
N=Integer.parseInt(st.nextToken()); // 정점의 개수
M=Integer.parseInt(st.nextToken()); // 간선의 개수
V=Integer.parseInt(st.nextToken()); // 시작 정점
arr=new int[N+1][N+1];
for(int i=0;i<M;i++){
st=new StringTokenizer(br.readLine());
int u=Integer.parseInt(st.nextToken());
int v=Integer.parseInt(st.nextToken());
arr[u][v]=arr[v][u]=1;
}
visited=new boolean[N+1];
DFS(V);
System.out.println();
visited=new boolean[N+1];
BFS(V);
}
public static void DFS(int start){
visited[start]=true;
System.out.print(start+" ");
for (int i=1;i<N+1;i++){
if(arr[start][i]==1 && visited[i]==false){
DFS(i);
}
}
}
public static void BFS(int start){
Queue<Integer> q=new LinkedList<>();
q.add(start);
visited[start]=true;
while (!q.isEmpty()){
int num=q.poll();
System.out.print(num+" ");
for(int i=1;i<N+1;i++){
if(arr[num][i]==1 && visited[i]==false){
q.add(i);
visited[i]=true;
}
}
}
}
}
|
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 2667번 : 단지번호붙이기 (0) | 2021.11.25 |
|---|---|
| [백준] 2178번 : 미로 탐색 (0) | 2021.11.25 |
| [백준] 1080번 : 행렬 (0) | 2021.11.24 |
| [백준] 16953번 : A -> B (0) | 2021.11.24 |
| [백준] 1744번 : 수 묶기 (0) | 2021.11.23 |
