백준 1260(DFS와 BFS) C언어

DFS와 BFS 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

165267

58466

34469

34.739%

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 복사

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 복사

1 2 4 3
1 2 3 4

예제 입력 2 복사

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2 복사

3 1 2 5 4
3 1 4 2 5

예제 입력 3 복사

1000 1 1000
999 1000

예제 출력 3 복사

1000 999
1000 999

 

<코드>

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 1001
int graph[MAX][MAX] = { 0 }; //그래프의 인접 행렬
int DFS_V[MAX] = { 0 }; //방문한(출력한) 정점 표시 
int BFS_V[MAX] = { 0 }; //방문한(출력한) 정점 표시
int que[MAX] = { 0 }; //너비 우선 탐색에 사용될 큐
void dfs(int V, int N);
void bfs(int V, int N);
int main(void)
{
	int N, M, V, i, j;
	scanf("%d %d %d", &N, &M, &V);
	while (M--) {
		scanf("%d %d", &i, &j);
		graph[i][j] = 1; 
		graph[j][i] = 1;
	}
	dfs(V, N);
	printf("\n");
	bfs(V, N);
			return 0;
}
void dfs(int V, int N) //깊이 우선 탐색
{
	int W; 
	printf("%d ", V);
	DFS_V[V] = 1;
	for (W = 1; W <= N; W++) {
		if (graph[V][W] == 1 && DFS_V[W] == 0)
			dfs(W, N);
	}
}
void bfs(int V, int N) //너비 우선 탐색
{
	int W;
	int front, rear, pop;
	front = rear = 0;
	printf("%d ", V);
	BFS_V[V] = 1;
	que[rear++] = V; 
	while (front < rear) {
		pop = que[front++]; 
		for (W = 1; W <= N; W++) {
			if (graph[pop][W] == 1 && BFS_V[W] == 0) {
				printf("%d ", W);
				BFS_V[W] = 1;
				que[rear++] = W;
			}
		}
	}
}

 

<풀이>

  깊이우선탐색(DFS)은 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법으로, 후입선출 구조의 스택을 사용한다. 위의 코드에서는 재귀함수를 사용하여 스택의 역할을 구현하였다.

  너비우선탐색(BFS)은 시작 정점 v를 결정하여 방문한 후, 정점 v에 인접한 정점 중에서 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue하고, 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해 큐에서 deQueue하여 받은 정점을 v로 설정하고 앞의 과정을 반복한다. 이 과정을 큐가 공백이 될 때까지 반복한다.