반응형
https://www.acmicpc.net/problem/1260
💡 DFS와 BFS
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
[입력]
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
[출력]
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
✅ 문제 풀이
- DFS와 BFS의 로직을 나누어서 두번의 결과를 따로 구하고 출력하도록 하였다.
- 일단 입력으로 받은 간선의 정보를 2차원 벡터에 저장하였다.
이때 양방향 간선이라는 점을 고려하여, A->B로 B->A로의 간선 정보를 저장해준다. - S노드에서 시작하므로, S번의 visited를 true로 설정하고 시작한다.
- 간선 정보를 담은 arr배열을, 각 노드에 대해서 오름차순 정렬해준다. 노드 번호가 낮은 것부터 방문해야 하기 때문이다.
- dfs함수는, arr배열의 s번 vector를 탐색하는데, 먼저 방문하는 노드를 시작으로 또 dfs를 재귀호출하며 방문하도록 한다.
- bfs함수는, arr배열의 s번 vector를 탐색하는데, 각 노드를 탐색할 때마다 queue에 담아주고, 해당 벡터를 다 탐색하고 나서는 queue의 front부터 탐색하며 bfs를 재귀호출하도록 한다.
- 각각의 결과는 dfs_result, bfs_result에 담은 후 출력한다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
void dfs(int s, vector<vector<int>> arr, vector<bool> &visited, vector<int> &dfs_result) {
for (int i = 0; i < arr[s].size(); i++) {
if (!visited[arr[s][i]]) {
visited[arr[s][i]] = true;//방문
dfs_result.push_back(arr[s][i]);
dfs(arr[s][i], arr, visited, dfs_result);
}
}
}
void bfs(int S, vector<vector<int>> arr, vector<bool> &visited, vector<int> &bfs_result, queue<int> &q) {
for (int i = 0; i < arr[S].size(); i++) {
if (!visited[arr[S][i]]) {
visited[arr[S][i]] = true;//방문
q.push(arr[S][i]);
bfs_result.push_back(arr[S][i]);
}
}
while (!q.empty()) {
int next = q.front();
q.pop();
bfs(next, arr, visited, bfs_result, q);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, S;
cin >> N >> M >> S;
vector<vector<int>> arr(N+1);
vector<bool> visited1(N + 1, false);//dfs에서사용
vector<bool> visited2(N + 1, false);//bfs에서사용
queue<int> q;//bfs에서 사용
vector<int> dfs_result;
vector<int> bfs_result;
for (int i = 0; i < M; i++) {//간선 정보 입력받기
int n1, n2;
cin >> n1 >> n2;
arr[n1].push_back(n2);
arr[n2].push_back(n1);
}
for (int i = 1; i < N + 1; i++) {//노드별로 간선 정보를 오름차순 정렬
sort(arr[i].begin(), arr[i].end());
}
visited1[S] = true;
visited2[S] = true;
dfs_result.push_back(S);
bfs_result.push_back(S);
dfs(S, arr, visited1, dfs_result);
bfs(S, arr, visited2, bfs_result, q);
for (int i = 0; i < dfs_result.size(); i++) {
cout << dfs_result[i]<<" ";
}
cout << "\n";
for (int i = 0; i < bfs_result.size(); i++) {
cout << bfs_result[i] << " ";
}
return 0;
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 1388번 C++ "바닥 장식" 풀이 / 구현 문제 (0) | 2023.12.09 |
---|---|
[백준] 1759번 C++ "암호 만들기" 풀이 / 백트래킹 (2) | 2023.12.08 |
[백준] 1049번 C++ "기타줄" 풀이 / 그리디 알고리즘 (1) | 2023.12.05 |
[백준] 1439번 C++ "뒤집기" 풀이 / 문자열처리 (1) | 2023.12.04 |
[백준] 1475번 C++ "방 번호" 풀이 / 구현 (1) | 2023.12.03 |