728x90
https://www.acmicpc.net/problem/1260
문제 분석
입력을 받아 그래프를 만들고, DFS로 탐색 하였을때와 BFS로 탐색하였을때 각각 출력해주는 형태의 문제이다.
이 문제는 DFS와 BFS를 이해하고 있다면 문제 없을거라고 생각한다.
코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
void DFS(int index);
void BFS(int index);
vector<vector<int>> graph;
vector<bool> visited;
int n, m, v;
int main()
{
int input1, input2;
cin >> n >> m >> v;
graph.resize(n + 1);
visited = vector<bool>(n + 1, false);
while (m--)
{
cin >> input1 >> input2;
graph[input1].push_back(input2);
graph[input2].push_back(input1);
}
for (int i = 1; i < graph.size(); ++i)
sort(graph[i].begin(), graph[i].end());
DFS(v);
cout << '\n';
visited = vector<bool>(n + 1, false);
BFS(v);
}
void DFS(int index)
{
if (visited[index])
return;
visited[index] = true;
cout << index << ' ';
for (int j : graph[index])
DFS(j);
}
void BFS(int index)
{
queue<int> que;
que.push(index);
visited[index] = true;
while (!que.empty())
{
int current = que.front();
que.pop();
cout << current << ' ';
for (int i : graph[current])
{
if (visited[i])
continue;
visited[i] = true;
que.push(i);
}
}
}
728x90
'ALGORITHM > C++ - 백준' 카테고리의 다른 글
[백준 14940] 쉬운 최단거리 (0) | 2023.10.18 |
---|---|
[백준 16928] 뱀과 사다리 게임 (1) | 2023.10.18 |
[백준 10026] 적록색약 (1) | 2023.10.18 |
[백준 24479] 알고리즘 수업 - 깊이 우선 탐색 1 (0) | 2023.08.01 |
[백준 11724] 연결 요소의 개수 (0) | 2023.08.01 |
댓글