[C++] 백준 1260번 - DFS와 BFS

 

 

예전에 공부했지만 까먹은 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 문제를 풀어보려고 한다.

DFS와 BFS는 그래프를 탐색하는 방법이다. 여기서 그래프는 정점과 그 정점을 연결하는 간선으로 이루어진 자료구조를 말한다.

 

DFS는 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동한다.

BFS는 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동한다.

 

문제 1260번

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

1260번: DFS와 BFS

 

예전에 해본건데 안 하니까 또 까먹었다...

다시 예전에 했던 것을 공부하고 작성했다.

 

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

bool visited[1001];
vector<int> node[1001];
int n, m, v;

void reset() {
	for (int i = 1; i <= n; i++) {
		visited[i] = 0;
	}
}

void dfs(int x) {
	visited[x] = true;
	cout << x << ' ';
	for (int i = 0; i < node[x].size(); i++) {
		int y = node[x][i];
		if (!visited[y])
			dfs(y);
	}
}

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << ' ';
		for (int i = 0; i < node[x].size(); i++) {
			int y = node[x][i];
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
			}
		}
	}
}

int main(void) {
	int k, w;
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		cin >> k >> w;
		// 양방향
		node[k].push_back(w);
		node[w].push_back(k);
	}

	// 넣은 것을 오름차순으로
	for (int i = 1; i <= n; i++) {
		sort(node[i].begin(), node[i].end());
	}
	dfs(v);
	reset();
	cout << '\n';
	bfs(v);
}