1260번: DFS와 BFS

1260번: DFS와 BFS(BOJ C/C++)

사용 언어: C

문제

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

입력

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

출력

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

 

풀이

DFS, BFS (행렬로 구현) 글에서 따로따로 인접 행렬로 구현한 DFS, BFS 코드들을 하나로 합친 코드다.

#include <stdio.h>
#define MAX 1001

int graph[MAX][MAX]={0,}; //인접행렬
int visitedDFS[MAX]={0,}; //DFS 방문했는지 check
int visitedBFS[MAX]={0,}; //BFS 방문했는지 check
int queue[MAX] = {0,};

void DFS(int v, int N)
{
	visitedDFS[v]=1; //방문한 곳: 1
	printf("%d ", v); //정점 출력
	for(int i=1; i<=N; i++)
	{
		if(graph[v][i] && !visitedDFS[i]) //인접여부 확인 && 정점의 방문 여부
			DFS(i, N); //재귀 함수
	}
}

void BFS(int v, int N)
{
	int pop, front, rear;
	front = rear = -1;
	visitedBFS[v] = 1; //방문한 곳: 1
	queue[++rear] = v; //큐->push
	while(front < rear)
	{
		pop = queue[++front]; //큐->pop
		printf("%d ",pop);
		for(int i=1; i<=N; i++)
		{
			if(graph[pop][i] && !visitedBFS[i]) //인접여부 확인 && 정점의 방문 여부
			{
				visitedBFS[i] = 1;
				queue[++rear] = i; //큐->push
			}
		}
	}
}

int main(void)
{
	int N,M,v; // 정점개수, 간선개수, 시작정점
	int x,y; // 좌표
	scanf("%d %d %d", &N, &M, &v);
	
	//간선개수만큼 반복
	while(M--)
	{
		scanf("%d %d", &x,&y);
		//인접행렬 만들기
		graph[x][y]=1;
		graph[y][x]=1;
	}
	DFS(v, N);
	printf("\n");
	BFS(v, N);
	printf("\n");
	return 0;
}