1260 : 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부터 방문된 점을 순서대로 출력하면 된다.

---

접근

---

코드

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int v = sc.nextInt();

		int[][] a = new int[n + 1][n + 1];
		boolean[] c = new boolean[n + 1];

		for (int i = 1; i <= m; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();
			a[v1][v2] = 1;
			a[v2][v1] = 1;
		}

		dfs(a, c, v);
		System.out.println();
		Arrays.fill(c, false);
		bfs(a, c, v);

		sc.close();
	}

	//재귀함수를 이용한 DFS
	public static void dfs(int[][] a, boolean[] c, int v) {
		int n = a.length - 1;
		c[v] = true;
		System.out.print(v + " ");
		for (int i = 1; i <= n; i++) {
			if (a[v][i] == 1 && !c[i])
				dfs(a, c, i);
		}
	}

	//큐를 이용한 BFS
	public static void bfs(int[][] a, boolean[] c, int v) {
		Queue<Integer> q = new LinkedList<Integer>();
		int n = a.length - 1;
		q.add(v);
		c[v] = true;
		while (!q.isEmpty()) {
			v = q.poll();
			System.out.print(v + " ");
			for (int i = 1; i <= n; i++) {
				if (a[v][i] == 1 && !c[i]) {
					q.add(i);
					c[i] = true;
				}
			}
		}
	}

}