득이공간
[백준 C++] 1260 DFS와 BFS - 깊이우선탐색, 너비우선탐색 본문
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> Neighbors;
vector<bool> CheckList;
queue<int> SearchQueue;
vector<int> DFS;
vector<int> BFS;
void DFSFunc(int Node)
{
CheckList[Node] = true;
DFS.emplace_back(Node);
for (const int& Neighbor : Neighbors[Node])
{
if (!CheckList[Neighbor])
{
DFSFunc(Neighbor);
}
}
}
void BFSFunc(int Node)
{
// First Node
CheckList[Node] = true;
BFS.emplace_back(Node);
for (const int& Neighbor : Neighbors[Node])
{
if (!CheckList[Neighbor])
{
SearchQueue.push(Neighbor);
}
}
while (!SearchQueue.empty())
{
int SearchNode = SearchQueue.front();
SearchQueue.pop();
if (CheckList[SearchNode])
{
continue;
}
CheckList[SearchNode] = true;
BFS.emplace_back(SearchNode);
for (const int& Neighbor : Neighbors[SearchNode])
{
if (!CheckList[Neighbor])
{
SearchQueue.push(Neighbor);
}
}
}
}
int main()
{
int N, M, V;
cin >> N >> M >> V;
// 0. Allocation
Neighbors.reserve(N);
for (int i = 0; i < N; ++i)
{
Neighbors.emplace_back(vector<int>());
}
for (int i = 0; i < M; ++i)
{
int Source, Destination;
cin >> Source >> Destination;
Neighbors[Source - 1].emplace_back(Destination - 1);
Neighbors[Destination - 1].emplace_back(Source - 1);
}
for (vector<int>& CurrentNodeNeighbors : Neighbors)
{
sort(CurrentNodeNeighbors.begin(), CurrentNodeNeighbors.end());
}
// 1. DFS Algorithm
DFS.reserve(N);
CheckList.reserve(N);
for (int i = 0; i < N; ++i)
{
CheckList.emplace_back(false);
}
DFSFunc(V - 1);
for (const int& node : DFS)
{
cout << node + 1 << ' ';
}
cout << '\n';
// 2. BFS Algorithm
BFS.reserve(N);
CheckList.clear();
for (int i = 0; i < N; ++i)
{
CheckList.emplace_back(false);
}
BFSFunc(V - 1);
for (const int& node : BFS)
{
cout << node + 1 << ' ';
}
}
문제 이름대로 DFS, BFS 알고리즘을 한 번씩 수행하면 됩니다.
인접 리스트를 생성하고나서 각 리스트 마다 오름차순 정렬을 해준 후에
각 알고리즘을 수행했습니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 C++] 2108 통계학 - 정렬 (1) | 2024.01.28 |
|---|---|
| [백준 C++] 2178 미로 탐색 - 너비우선탐색 (1) | 2024.01.28 |
| [백준 C++] 2667 단지번호붙이기 - 깊이우선탐색 (1) | 2024.01.24 |
| [백준 C++] 2606 바이러스 - 깊이우선탐색 (1) | 2024.01.24 |
| [백준 C++] 1931 회의실 배정 - 그리디 (0) | 2024.01.23 |
'PS/알고리즘 문제풀이' Related Articles
more
