[백준 알고리즘] 1260번 DFS와 BFS

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

1260번: DFS와 BFS

입력

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

출력

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

 

풀이

1) DFS (깊이 탐색 알고리즘)

    - 전 구간을 탐색한다. 

    - stack이나 재귀함수(OS 자체가 스택 기반이므로)를 이용한다.

 

2) BFS (너비 탐색 알고리즘)

    - 가까운 정점부터 이동한다.

    - Queue를 이용한다.

    - 하나의 정점을 기준으로 연결 된 모든 정점부터 방문한다. 

 

 

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

vector<int> CommonArray[1000];
queue<int> que;

bool dfsvisit[1000] = { false }; 
bool bfsvisit[1000] = { false };


void dfs(int sp) {

	dfsvisit[sp] = true;
	cout << sp << " ";
	for (int i = 0; i < CommonArray[sp].size(); i++) {

		int temp = CommonArray[sp][i];
		if (dfsvisit[temp] == false) { 
			dfs(CommonArray[sp][i]);
		}
		
	}



}

void bfs(int sp) {

	bfsvisit[sp] = true;
	que.push(sp); // 최초 시작점 큐 푸시 및 방문 표시
	while (!que.empty()) {
		sp = que.front(); 큐에서 가장 첫번째 방문할 정점
		cout << sp << " ";
		que.pop();
		for (int i = 0; i < CommonArray[sp].size(); i++) { //연결 되어 있는 모든 정점 방문하기.
			int temp = CommonArray[sp][i];
			if (bfsvisit[temp] == false) {
				bfsvisit[temp] = true;
				que.push(temp);
			}
		}



	}

}
int main() {

	//정점, 간선, 탐색을 시작할 정점의 번호
	int N = 0;
	int M = 0;
	int V = 0;
	
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {

		int startPoint = 0;
		int finishPoint = 0;

		cin >> startPoint >> finishPoint;

		CommonArray[startPoint].push_back(finishPoint);
		CommonArray[finishPoint].push_back(startPoint);

	}

	//바이너리 트리나 그래프는 정렬 된 상태이어야 한다. 중요하다!!
	for (int i = 1; i <= N; i++) {
		sort(CommonArray[i].begin(), CommonArray[i].end());
	}


	dfs(V);
	cout << endl;
	bfs(V);


}

 

끝.

 

여기서 더 나아가서 #include<alogorithm>의 sort 메소드는 quick sort로 정렬되는데 이 부분 직접 구현해보는 것은 숙제로 남기겠다.