BOJ 1260. DFS와 BFS

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

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static boolean[][] edge;
	static boolean[] visited;

	static void dfs(int from) {
		visited[from] = true;
		System.out.print(from + " ");

		for (int to = 1; to <= N; to++) {
			if \(!edge\[from]\[to] \|| visited\[to])
				continue;

			visited[to] = true;
			dfs(to);
		}
	}

	static void bfs(int start) {
		Queue<Integer> q = new ArrayDeque<>();
		q.offer(start);
		visited[start] = true;

		while (!q.isEmpty()) {
			int from = q.poll();
			System.out.print(from + " ");
			for (int to = 1; to <= N; to++) {
				if \(!edge\[from]\[to] \|| visited\[to])
					continue;

				visited[to] = true;
				q.offer(to);
			}
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		edge = new boolean[N+1][N+1];
		visited = new boolean[N+1];
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			edge[from][to] = edge[to][from] = true;
		}
		dfs(V);
		System.out.println();

		Arrays.fill(visited, false);
		bfs(V);
	}
}