[BOJ] 백준_1260번_DFS와 BFS_C/C++백준 알고리즘2022. 1. 26. 10:00
목차
문제 출처
https://www.acmicpc.net/problem/1260
문제 설명
코드
//[BOJ] 1260번 DFS와 BFS
#include<iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
vector<int> Graph[1001];
queue<int> q;
bool visited[1001];
//첫째항만 설명
void dfs(int a)
{
visited[a] = true; // visited[1] = true
cout << a << " ";
for (int i = 0; i < Graph[a].size(); i++) // Graph[1].size = 노드 1의 주변 노드의 개수
{
int b = Graph[a][i]; // b = Graph[1][0] = 2
if (!visited[b]) // visited[2] 는 false이므로 dfs(2) 실행
dfs(b);
}
}
void bfs(int start)
{
q.push(start); // q.push(1)
visited[start] = true; // visited[1] = true
while (!q.empty()) // 큐가 빌 때 까지
{
int a = q.front(); // int a = 큐의 맨 처음 = 1, a = 1
q.pop(); // 큐에 1 하나밖에 없으므로 1 pop시킴
cout << a << " "; // pop된 1 출력
for (int i = 0; i < Graph[a].size(); i++) // Graph[1].size = 노드 1의 주변 노드의 개수
{
int b = Graph[a][i]; // b = Graph[1][0]; 이전에 Graph를 정렬했으므로
if (!visited[b]) { // Graph[1][0] 은 노드 1의 주변 노드들 중 다음으로 큰 수
q.push(b); // ex) b = 2였다면 2를 큐에 삽입하고
visited[b] = true; // 노드 2를 방문 처리
}
}
}
}
int main()
{
cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
int n, m, v;
cin >> n >> m >> v;
for (int i = 0; i < m; i++)
{
int p, q;
cin >> p >> q;
Graph[p].push_back(q); // 노드 p 그래프에 q를 추가하고
Graph[q].push_back(p); // 노드 q 그래프에 p를 추가한다. 두 노드는 이어져 있다.
}
for (int i = 1; i <= n; i++)
sort(Graph[i].begin(), Graph[i].end()); // Graph를 크기 순 대로 정렬
dfs(v); cout << endl; // 시작 노드가 v 이므로 v를 전달
memset(visited, false, sizeof(visited)); // bfs할 때 visited를 또 쓰기 때문에 모든 값 false로 메모리 초기화
bfs(v); cout << endl;
return 0;
}
풀이 과정
먼저 각 노드(정점)들을 표현하는 벡터 Graph, bfs 탐색에 사용하는 큐 q, 방문 여부를 표시하는 bool형 배열 visited를 만들어준다. dfs는 깊이 우선 탐색으로서 재귀함수나 스택으로 구현할 수 있다. 위 코드에서는 재귀함수를 사용해 구현하였다. 노드를 한없이 깊게 탐색할 수 있게 되는 단점이 있지만 깊은 단계에 위치한 목표 노드에 비교적 빨리 도달할 수 있다. 현재 노드의 주변 노드들 중 방문했었던 노드를 제외하고 더 깊은 단계의 노드로 넘어가면서 탐색한다. 재귀적으로 진행되기 때문에 앞서 sort함수로 오름차순 정렬해주는 과정이 작은 수 부터 탐색한다는 조건에 있어서 매우 중요하다. bfs는 너비 우선 탐색으로서 큐(Queue)를 이용하여 구현할 수 있다. 현재 노드 주변 노드들을 크기순으로 큐에 삽입한 뒤 하나씩 방문하며 출력하고 pop 시키는 구조로 작성하였다. bfs 역시 큐에 인접 노드들을 삽입할 때 크기순으로 삽입하는 조건이 있기 때문에 사전에 sort함수로 오름차순 정렬이 필요하다.
728x90
반응형
LIST
'백준 알고리즘' 카테고리의 다른 글
[BOJ] 백준_1543번_문서 검색_C/C++ (0) | 2022.01.31 |
---|---|
[BOJ] 백준_2847번_게임을 만든 동준이_C/C++ (0) | 2022.01.27 |
[BOJ] 백준_1449번_수리공 항승_C/C++ (0) | 2022.01.25 |
[BOJ] 백준_5585번_거스름돈_C/C++ (0) | 2022.01.23 |
[BOJ] 백준_22864번_피로도(재채점)_C/C++ (0) | 2022.01.22 |
@kdj :: Childev'note
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!