//코드 참조 사이트: http://javannspring.tistory.com/174
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
|
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class DfsAndBfs {
//간선이 있는지 여부를 표시해줄 2차원 배열
static boolean[][] graph = new boolean[1001][1001];
//visited[target]에 방문했는지 여부 체크
static boolean visited[] = new boolean[10001];
static int N, M, start;
static void doDfs(int start) {
visited[start] = true;
System.out.print(start + " ");
for(int i = 1; i <= N; i++) {
if(graph[start][i] == true && visited[i] == false) doDfs(i);
}
}
static void doBfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
System.out.print(start + " ");
int tmp = 0;
while(!q.isEmpty()) {
tmp = q.poll();
for(int i = 1; i <= N; i++) {
if(graph[tmp][i] == true&& visited[i] == false) {
q.offer(i);
visited[i] = true;
System.out.print(i + " ");
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
start = sc.nextInt();
Arrays.fill(visited, false);
int x = 0;
int y = 0;
for(int i = 0; i < M; i++) {
x = sc.nextInt();
y = sc.nextInt();
graph[x][y] = graph[y][x] = true;
}
doDfs(start);
Arrays.fill(visited, false);
System.out.println("");
doBfs(start);
}
}
| cs |
댓글 없음:
댓글 쓰기