[C++] BOJ 1260 - DFS와 BFS

#include <iostream>
#include <queue>

using namespace std;

int graph[1001][1001];
int check[1001] = {0,};
queue<int> q;

void DFS(int start, int max) {
	printf("%d ",start);
	check[start] = 1;
	
	for(int i=1;i<=max;i++) {
		if(graph[start][i] == 1 && !check[i]) {
			check[i] = 1;
			DFS(i,max);
		}
	}
}

void BFS(int start, int max) {
	
	for(int i=0;i<=max;i++) 
		check[i] = 0;
	
	q.push(start);
	check[start] = 1;
	
	while(!q.empty()) {
		int current = q.front();
		q.pop();
		
		printf("%d ",current);
		
		for(int i=1;i<=max;i++) {
			if(graph[current][i] == 1 && !check[i]) {
				check[i] = 1;
				q.push(i);
			}
		}
	}
}

int main() {
	int N,M,V;
	
	scanf("%d %d %d",&N,&M,&V);
	
	for(int i=0;i<M;i++) {
		int u,v;
		scanf("%d %d",&u,&v);
		
		graph[u][v] = 1;
		graph[v][u] = 1;
	}
	
	
	DFS(V,N);
	printf("\n");
	BFS(V,N);
}

DFS와 BFS의 사용법을 익히는 문제입니다.

간단히 설명을 끄적이자면, 

트리(or 그래프)의 대표적인 탐색 방법 두가지에는

DFS(Depth First Search, 깊이 우선 탐색) : 정점과 이어진 간선을 쭉 따라가다 더이상의 정점과 이어지지 않으면 이전의 정점으로 돌아와 다른 길로 우회하면서 탐색하는 방법. 주로 스택을 이용하여 구현함.

BFS(Breadth First Search, 너비 우선 탐색) : 큐를 이용해 이어지는 간선을 push pop함으로써 탐색하는 방법.

이라고 할 수 있겠습니다.

위 코드는 무방향 그래프를 인접 행렬로써 정점과 간선을 입력받고 DFS와 BFS를 사용하여 탐색 과정을 출력해주는 예제입니다.

이 문제를 풀면서 중요한게 하나 있습니다. 문제를 보시면 "단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다." 라는 조건이 존재합니다. 따라서 저처럼 인접 행렬로 for문을 이용해 정점 번호가 작은 것부터 탐색하지 않고 인접 리스트를 사용하셨다면 오름차순으로 정렬하실 필요가 있습니다. vector로 푸셨다면 sort(vector_name.begin(), vector_name.end())를 사용하셔야 되겠습니다.

앞으로 DFS BFS문제 풀때 유용하게 Ctrl+C,V.. 가 아니라 참고용..으로 쓰시길 바랍니다 :)