[백준] 1260번 - DFS와 BFS (C언어) [Silver2]

input1	output1	input1	output1
4 5 1 1 2  1 3 1 4 2 4 3 4	1 2 4 3 1 2 3 4	5 5 3 5 4 5 2 1 2 3 4 3 1	3 1 2 5 4 3 1 4 2 5

해당 문제는 DFS와 BFS로 간선들을 탐색한 결과를 정점 번호로 출력하는 문제이다. 해당 문제를 해결하기 위해서는 DFS와 BFS의 개념을 알고 있어야 한다.

 DFS(깊이 우선 탐색)이란 트리의 깊은 부분을 먼저 탐색한다는 개념으로 볼 수 있다. DFS는 스택 혹은 재귀함수를 이용한다. DFS는 각 노드를 탐색할 때 주로 사용된다. 동작 과정은 아래와 같다.

1. 첫 시작 노드(루트 노드)를 스택에 삽입하고 방문 표시를 한다.
2. 스택의 최상단 노드를 확인하고 그 노드와 인접한 노드를 스택에 삽입하고 방문 표시를 한다. 만약 인접하는 노드가 없다면 스택에서 최상단 노드를 뺀다.
3. 위 과정을 반복한다.

---

 BFS(너비 우선 탐색)이란 트리의 너비를 기준으로 탐색한다는 개념으로 볼 수 있다. BFS는 최단 경로를 찾는 경우에 많이 사용된다. BFS는 자료구조 중에서 큐를 사용한다. BFS 동작 과정은 아래와 같다.

1. 첫 시작 노드(루트 노드)를 큐에 삽입하고 방문 표시를 한다.
2. 큐에서 하나의 노드를 꺼낸다. 해당 노드와 연결된 노드중 방문하지 않는 노드를 방문하고 큐에 삽입한다.
3. 2번 과정을 반복해서 큐가 비어있을 때 까지 반복한다.

---

전체 소스 코드는 아래와 같다.  (C언어로 작성하였지만 큐와 스택을 전부 구현하지 않고 DFS는 재귀함수로 BFS는 큐를 재현하여 풀이하였다.)

#include <stdio.h>
#include <stdbool.h>
#pragma warning(disable:4996)

int visited[1001] = { 0, }; // 방문 표시 초기화
int graph[1001][1001] = { 0, }; // 그래프 초기화
int queue[1001]; 

void dfs(int v,int n) { // 깊이 우선 탐색
	visited[v] = true;
	printf("%d ", v);
	for (int i = 1; i <= n; i++) {
		if (graph[v][i] && !visited[i]) // 그래프에 방문하지 않았고 간선 존재
			dfs(i, n);
	}
}

void bfs(int v, int n) { // 너비 우선 탐색
	/* 큐 변수 선언 */
	int front = 0;
	int rear = 1;
	int pop;

	visited[v] = true;
	printf("%d ", v);
	queue[0] = v;
	while (front < rear) { // 큐가 비어있으면 반복 종료 
		pop = queue[front++]; // dequeue 연산
		for (int i = 1; i <= n; i++){
			if (graph[pop][i] && !visited[i]) {
				visited[i] = true;
				printf("%d ", i);
				queue[rear++] = i; // enqueue 연산
			}
		}
	}
}

int main() {
	int n,m, v;

	scanf("%d%d%d", &n, &m, &v);

	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		graph[x][y] = 1; // 양방향 그래프
		graph[y][x] = 1;
	}

	visited[v] = true;
	dfs(v,n);

	for (int i = 1; i <= n; i++) // 방문 노드 초기화
			visited[i] = false;
	visited[v] = true;
	printf("\n");
	bfs(v, n);

	return 0;
}