[실 2][C++] 백준 1260번 DFS와 BFS

문제

1260번: DFS와 BFS (acmicpc.net)

 

풀이

dfs는 재귀를 사용했고 bfs 는 queue를 사용하여 구현했다.

주의할 점은 한 노드에 노드가 여러개 연결돼있다면 작은 번호 순으로 방문한다는 조건을 잊지 않는 것이다.

(이 조건 때문에 첫,두번째 제출이 틀렸음. 그래서 sort 함수를 사용하여 노드를 정렬하고 bfs,dfs를 실행했다.) 

 

코드

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

using namespace std;

vector<vector<int>> graph(1001);//각node에 연결된  node들
bool nodeVisit[1001] = {false};
vector<int> answer;
queue<int> q;

void dfs(int curNode) {
	nodeVisit[curNode] = true;
	answer.push_back(curNode);
	for (int i = 0; i < graph[curNode].size(); i++) {
		int nextNode = graph[curNode][i];
		if (!nodeVisit[nextNode]) {//새로 감염된 컴퓨터라면 카운트.
			nodeVisit[nextNode] = true;
			dfs(nextNode);
		}

	}
}

void bfs(int startNode) {
	q.push(startNode);
	nodeVisit[startNode] = true;
	while (!q.empty()) {
		int curNode = q.front();
		for (int i = 0; i < graph[curNode].size(); i++) {
			int nextNode = graph[curNode][i];
			if (!nodeVisit[nextNode]) {//새로 감염된 컴퓨터라면 카운트.
				nodeVisit[nextNode] = true;
				q.push(nextNode);
			}
		}
		answer.push_back(curNode);
		q.pop();
	}
	return;
}

int main() {
	int nodeNum, connNum,startNode;
	cin >> nodeNum >> connNum>> startNode;

	//graph 만들기
	int nOne, nTwo;
	for (int i = 0; i < connNum; i++) {
		cin >> nOne >> nTwo;
		graph[nOne].push_back(nTwo);
		graph[nTwo].push_back(nOne);
	}
	//작은 순으로 연결된 node정렬
	for (int i = 1; i <= nodeNum; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	//dfs 시작
	dfs(startNode);

	//dfs 답 출력
	for (int i = 0; i < answer.size(); i++) {
		int curNode = answer[i];
		cout << curNode << " ";
		nodeVisit[curNode] = false;
	}
	cout << endl;
	answer.clear();

	//bfs 시작
	bfs(startNode);

	//bfs 답 출력
	for (int i = 0; i < answer.size(); i++) {
		int curNode = answer[i];
		cout << curNode << " ";
		nodeVisit[curNode] = false;
	}

	return 0;
}