[C++] 백준 1260 DFS와 BFS

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

using namespace std;

const int vertexMax = 1001;	//최대 노드 개수
vector<int> num[vertexMax];
bool visited[vertexMax]{false};	//방문한 노드

void DFS(int curr);
void BFS(int curr);

int main()
{
	ios::sync_with_stdio(false);

	int vertex, line, startNum;

	cin >> vertex >> line >> startNum;

	for (int i = 0; i < line; i++)
	{
		int temp[2];
		cin >> temp[0] >> temp[1];

		num[temp[0]].push_back(temp[1]);	//무방향 그래프로 넣어준다.
		num[temp[1]].push_back(temp[0]);
	}

	//문제에서 순서에 따라 값이 달라지기에 작은 번호를 더 먼저 검사하도록한다.
	for (int i = 0; i < vertex; i++)
		sort(num[i].begin(), num[i].end());	

	DFS(startNum);
	cout << "\n";
	memset(visited, false, sizeof(visited));	//사용한 visited의 방문했는가를 초기화해준다.
	BFS(startNum);
}

void DFS(int curr)
{
	visited[curr] = true;	//현재 노드 방문

	cout << curr << " ";

	for (int i = 0; i < num[curr].size(); i++)
	{
		if (visited[num[curr][i]] == true) continue;	//다음 노드가 간 곳이면 패스

		DFS(num[curr][i]);	//다음 노드가 안 간 곳이면 다음 노드를 방문한다.
	}
}

void BFS(int curr)
{
	queue<int> q;
	q.push(curr);	//처음 갈 곳을 넣어준다.
	visited[curr] = true;
	cout << curr << " ";

	while (!q.empty())	//간 곳이 없을 때까지 반복
	{
		int currNode = q.front();	//현재 단계의 노드 값
		q.pop();	//현재 단계를 빼준다.

		for (int i = 0; i < num[currNode].size(); i++)	//현재 단계에 있는 노드 값들을 반복
		{
			int nextNode = num[currNode][i];	//현재 단계에 붙은 노드

			if (visited[nextNode] == false)
			{
				cout << nextNode << " ";	//다음 노드를 방문한다.
				visited[nextNode] = true;
				q.push(nextNode);	//다음 단계에서 쓸 수있게 노드를 넣어준다.
			}
		}
	}
}

 

풀이

1. DFS와 BFS를 이해하고 문제를 해결한다.
2. vector를 사용하여 노드들을 저장했다면 작은 값이 뒤에 있을 수도 있으므로 정렬해준다.

 

 

BFS와 DFS에 관한 설명 및 예시 주소

BFS : chanheess.tistory.com/45?category=1177428

DFS : chanheess.tistory.com/25?category=1177428