본문 바로가기

Problem Solving/Algorithm Training

[Baekjoon] 1260 - DFS와 BFS (C++)

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

 

1260번: DFS와 BFS

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

www.acmicpc.net

그래프 탐색 알고리즘의 가장 기본이라고 할 수 있는 DFS(depth-first search)와 BFS(breadth-first search)를 단순히 구현만 하면 되는 간단한 문제입니다. 그래프의 경우 입력으로 들어오는 정점의 개수가 최대 1,000개로 그리 크지 않기 때문에 인접 행렬(adjacency matrix) 방식으로 구현했습니다. DFS는 보통 재귀 함수를 사용해서 간단히 구현하는데 이번엔 연습 삼아 스택(stack)을 이용해 보았습니다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int n, m, v;
vector<vector<bool>> matrix;

void DFS()
{
	stack<int> vList;
	vector<bool> check(n + 1, false);

	// 시작할 정점의 번호 입력
	vList.push(v);

	while (!vList.empty()) {
		int vNum = vList.top();
		vList.pop();

		// 이미 방문한 정점이면 무시
		if (check[vNum]) {
			continue;
		}

		// 정점의 번호 출력 및 기록
		cout << vNum << " ";
		check[vNum] = true;

		// 정점 번호가 작은 것을 먼저 방문
		for (int i = n; i >= 1; i--) {
			if (vNum != i && matrix[vNum][i]) vList.push(i);
		}
	}
}

void BFS()
{
	queue<int> vList;
	vector<bool> check(n + 1, false);

	// 시작할 정점의 번호 입력 및 기록
	vList.push(v);
	check[v] = true;

	while (!vList.empty()) {
		int vNum = vList.front();
		vList.pop();
		
		// 정점의 번호 출력
		cout << vNum << " ";

		// 정점 번호가 작은 것을 먼저 방문
		for (int i = 1; i <= n; i++) {
			if (vNum != i && matrix[vNum][i] && !check[i]) {
				vList.push(i);
				check[i] = true;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> v;

	// 인접 행렬 방식으로 그래프 초기화
	for (int i = 0; i <= n; i++) {
		vector<bool> xList(n + 1, false);
		matrix.push_back(xList);
	}

	// 그래프 입력
	for (int i = 0; i < m; i++) {
		int v1, v2;
		cin >> v1 >> v2;

		// 양방향 간선임을 고려
		matrix[v1][v2] = true;
		matrix[v2][v1] = true;
	}

	// 결과 출력
	DFS();
	cout << "\n";
	BFS();
	cout << "\n";

	return 0;
}