백준 BOJ 1260 - DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

DFS는 깊이 우선 탐색으로, 스택이나 재귀를 사용하여 구현할 수 있다.

나는 재귀를 사용하여 구현했다.

BFS는 넓이 우선 탐색으로, 큐를 사용하여 구현할 수 있다.

 

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int dfsvisit[1234] = {0};
int bfsvisit[1234] = {0};

queue<int> q;

vector<int> v[1234];

void dfs(int node){
	dfsvisit[node] = 1;
	printf("%d ", node);
	
	for(int i=0; i<v[node].size(); i++){
		if(!dfsvisit[v[node][i]]) dfs(v[node][i]);
	}
	return;
}

void bfs(){
	while(!q.empty()){
		int tmp = q.front();
		bfsvisit[tmp] = 1;
		printf("%d ", tmp);
		q.pop();
		for(int i=0; i<v[tmp].size(); i++){
			if(!bfsvisit[v[tmp][i]]){
				q.push(v[tmp][i]);
				bfsvisit[v[tmp][i]] = 1;
			}
		}
	}
	return;
}

int main(){
	int n,m,V;
	int a,b;
	
	scanf("%d %d %d", &n, &m, &V);
	
	for(int i=0; i<m; i++){
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	q.push(V);
	
	for(int i=0; i<n; i++){
		if(v[i].size() != 0){
			sort(v[i].begin(), v[i].end());
		}
	}
	
	dfs(V);
	puts("");
	bfs();
}

우선 인접행렬을 vector<int> v[1234]로 구현해주었다.

메인함수부터 보자면

첫 포문에서 인접행렬을 만들고,

bfs를 위해 큐에 미리 시작노드를 푸시해준다.

그리고 숫자가 작은 노드부터 탐색한다는 조건이 있으니

std sort를 이용해 방문할수 있는 노드들을 정렬해준다음

dfs 출력,

한줄 내리고

bfs 출력을 하게 된다.

 

dfs를 살펴보자.

void dfs(int node){
	dfsvisit[node] = 1;
	printf("%d ", node);
	
	for(int i=0; i<v[node].size(); i++){
		if(!dfsvisit[v[node][i]]) dfs(v[node][i]);
	}
	return;
}

 

먼저 dfsvisit에 해당 노드를 방문하였다는걸 알려주고,

방문한 노드를 출력한다.

그리고 인접리스트를 순회하며

만약 방문하지않은 정점이 있다면

재귀함수를 통해 계속계속 탐색해주게 된다.

 

---

bfs를 살펴보자

void bfs(){
	while(!q.empty()){
		int tmp = q.front();
		bfsvisit[tmp] = 1;
		printf("%d ", tmp);
		q.pop();
		for(int i=0; i<v[tmp].size(); i++){
			if(!bfsvisit[v[tmp][i]]){
				q.push(v[tmp][i]);
				bfsvisit[v[tmp][i]] = 1;
			}
		}
	}
	return;
}

큐가 빌때까지 반복하는데,

탐색할 정점을 tmp에 저장 후,

tmp에 방문했다는것을 기록하고 출력해준다.

그다음 tmp를 뽑아내었으므로 큐의 원소 하나를 비워준다.

이후에는

tmp의 인접리스트를 순회하며

방문하지않은정점이 있다면 방문하라고 지시를 내려주는것 뿐이다.

여기서 주의할점은 지시를 내릴때도 방문기록을 남겨야 같은곳을 두번 방문하거나 하지 않는다.