백준 1260번: DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

 

문제

 

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

 

 

 

DFS: 깊이 우선 탐색

•시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법

•가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용

 

BFS: 너비 우선 탐색

시작 정점으로 부터 인접한 정점들을 모두 한 번씩 차례로 방문한 후, 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문

 

 

 

 

코드

 

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 1001;

int N, M, V; // N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점
int adj[MAX][MAX] = { 0, }; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

void dfs(int node) {
	cout<<node<<' ';

	for(int i = 1; i <= N; i++)
		if(adj[node][i] == 1 && visited[i] == 0) {
			visited[i] = 1;
			dfs(i);
		}
}

void bfs(int node) {
	queue<int> q;
	q.push(node);
	visited[node] = 1;

	while(!q.empty()) {
		int v = q.front();
		cout<<v<<' ';
		q.pop();

		for(int i = 1; i <= N; i++)
			if(adj[v][i] == 1 && visited[i] == 0) {
				visited[i] = 1;
				q.push(i);
			}
	}
}

int main(void) {
	cin>>N>>M>>V;

	int x, y; // 인접 행렬 좌표
	for(int i = 0; i < M; i++) {
		cin>>x>>y;
		adj[x][y] = 1;
		adj[y][x] = 1;
	}

	visited[V] = 1;
	dfs(V);
	cout<<'\n';


	// 방문 노드 초기화
	for(int i = 0; i <= N; i++) visited[i] = 0;
	visited[V] = 1;
	bfs(V);
}