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

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

1260번: DFS와 BFS

그래프 탐색 알고리즘의 가장 기본이라고 할 수 있는 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;
}