백준 1260 c++ "DFS와 BFS" -PlusUltraCode-

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

 

[필자 사고]

 

DFS 와 BFS 를 이용하여 문제를 해결해야 된다.

 

조건들을 확인해 보면 첫 번째로 여러개의 노드가 존재할 시 숫자가 작은 것부터 먼저 방문하라고 써져 있다.

 

즉 모든 노드들을 arr배열에 입력 받은뒤 해당되는 행에 sort 정렬 함수를 이용하여 필자는 오름차순으로 정리했다.

 

그다음 주의해야 할 사항들은 방문배열을 초개화 해줘야 된다.

 

소스코드는 아래와 같다.

 

[소스 코드]

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

using namespace std;

int N, M, V;

vector<vector<int>> arr;
vector<bool> visited;
vector<int> dfsTank;
vector<int> bfsTank;

void Input() {

	cin >> N >> M >> V;
	arr.resize(N + 1);

	visited.resize(N + 1, false);

	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; i++) {
		sort(arr[i].begin(), arr[i].end());
	}
}

void BFS(int startNum, vector<bool> &cVisited) {
	queue<int> q;
	q.push(startNum);
	cVisited[startNum] = true;
	bfsTank.push_back(startNum);
	while (!q.empty()) {
		int nowNum = q.front();
		q.pop();
		for (int nextNum : arr[nowNum]) {
			if (cVisited[nextNum] == true)continue;
			q.push(nextNum);
			cVisited[nextNum] = true;
			bfsTank.push_back(nextNum);
		}
	}
}

void DFS(int startNum, vector<bool>& cVisited) {
	if (cVisited[startNum] == true)return;

	cVisited[startNum] = true;
	dfsTank.push_back(startNum);

	for (int nextNum : arr[startNum]) {
		if (cVisited[nextNum] == true)continue;
		DFS(nextNum, cVisited);
	}
}

void GameStart() {
	vector<bool> copyVisited = visited;
	
	BFS(V, copyVisited);
	copyVisited = visited;
	DFS(V, copyVisited);

}

void Print() {
	for (int i = 0; i < dfsTank.size(); i++) {
		cout << dfsTank[i] << " ";
	}
	cout << '\n';
	for (int i = 0; i < bfsTank.size(); i++) {
		cout << bfsTank[i] << " ";
	}
}

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

	Input();
	GameStart();
	Print();
}