[백준/C++] DFS와 BFS_1260

📝 문제

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

💻 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, v;
queue<int> q;
vector<int> arr[1001];
int bfs_check[1001] = { 0, };
int dfs_check[1001] = { 0, };

void bfs() {
	while (!q.empty()){
		int now = q.front();
		q.pop();
		cout << now << " ";

		for (int i = 0; i < arr[now].size(); i++) {
			int next = arr[now][i];
			if (bfs_check[next]) continue;
			bfs_check[next] = 1;
			q.push(next);
		}

	}

}

void dfs(int now) {
	cout << now << " ";

	for (int i = 0; i < arr[now].size(); i++) {
		int next = arr[now][i];
		if (dfs_check[next]) continue;
		dfs_check[next] = 1;
		dfs(next);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> v;

	for (int i = 0; i < m; i++) {
		int start, end;
		cin >> start >> end;
		arr[start].push_back(end);
		arr[end].push_back(start);
	}

	for (int i = 0; i < n+1; i++) {
		sort(arr[i].begin(), arr[i].end());
	}

	q.push(v);
	bfs_check[v] = 1;
	dfs_check[v] = 1;

	dfs(v);
	cout << "\n";
	bfs();

	

	return 0;
}

💡 Point

• 문제에서 "이동 가능한 노드 중 가장 작은값"을 확인
• sort(vector.begin(), vertor.end())로 정렬 가능하다.
• 방문체크(check)를 2개 할 필요없다.