https://www.acmicpc.net/problem/1260
문제
> 그래프를 DFS, BFS로 탐색한 결과를 출력해라.
> 단 방문할 수 있는 정점이 여러개면 번호가 작은것먼저 방문하고 더 이상 방문 할 수 있는 점이 없으면 종료한다.
> 정점 수, 간선 수, 시작번호가 입력이다.
> M개의 줄엔 간선이 연결하는 두 정점의 번호가 주어진다.접근
DFS(Depth-First-search), BFS(Breadth-First-search)를 각각 구현해 주어진 노드, 간선, 시작점으로 탐색한다.
문제해결
> 점과 간선을 담을 이중벡터 dots와 방문처리를 위한 bool 벡터 dot을 선언해주고 BFS와 DFS를 함수로 구현한다.
> 문제에서 주어진 입력을 모두 받는다. 전역으로 선언한 벡터들을 assign을 통해 크기와 초기값을 지정해준다.
> 양방향 그래프이므로 입력받은 점, 간선에 대해 두가지로 벡터에 저장한다.
> 입력받은 점을 작은값부터 차례대로 탐색하기위해 정렬해주고 DFS와 BFS에 시작점으로 받은 V를 넣어 호출한다.
> 각 함수 사이에 fill을 이용해 dot 부울 벡터의 값을 다시 false로 전부 초기화 해줘야 제대로 값을 얻을 수 있다.문제해결(BFS)
> BFS는 큐를 사용하며 먼저 시작점을 입력받아 큐에 넣는다.
> 인접한 노드, 미방문 노드가 없으면 큐가 비기때문에 empty()가 될때 까지 while문을 돌린다.
> 큐의 가장 앞에있는 값을 먼저 탐색을 한다. 큐에서 제거해주면서 만약 탐색했던 점이면 다음 탐색으로 넘어가고 아니면 해당 점을 출력해주고 방문처리를 한다. 이제 해당 점의 갈 수 있는 경로를 전부 탐색해 방문한적 없는 경로만 큐에 넣는다.
> 위 탐색을 반복하면 탐색했던 점은 걸러지며 탐색 순서대로 출력이 나온다.문제해결(DFS)
> DFS는 스택 또는 재귀를 사용한다. 난 스택을 사용했다. 먼저 시작점을 입력받아 큐에 넣는다.
> 동작 자체는 BFS와 유사하다. 스택이 빌 때까지 반복해주며 스택에 들어온 값중 상단, 젤 나중에 들어온 값을 가져오고 제거한다. 스택은 LIFO(선입후출)이기 떄문이다.
> 그 점이 방문헀던 점이면 스택에 있는 다음 값으로 넘어가고 아니라면 해당 점의 다음 경로를 탐색한다.
> 문제에 방문할 수 있는 정점이 여러개면 번호가 작은 정점 부터 방문하라고 했으므로 해당 점의 가능 경로 중 큰수부터 스택에 넣기위해 역순으로 반복문을 돌려준다.(스택이므로)
> 방문했던 점이면 넘기고 안했으면 스택에 넣어준다.
> 위 과정을 반복한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
vector<vector<int>> dots;
vector<bool> dot;
void BFS(int start)
{
queue<int> q;
q.push(start);
while (!q.empty())
{
int d = q.front();
q.pop();
if (dot[d])
continue;
cout << d << " ";
dot[d] = true;
for (int i : dots[d])
{
if (!dot[i])
{
q.push(i);
}
}
}
}
void DFS(int start)
{
stack<int> s;
s.push(start);
while (!s.empty())
{
int d = s.top();
s.pop();
if (dot[d])
continue;
cout << d << " ";
dot[d] = true;
for (auto it = dots[d].rbegin(); it != dots[d].rend(); ++it)
{
if (!dot[*it])
s.push(*it);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M, V;
cin >> N >> M >> V;
dot.assign(N + 1, false);
dots.assign(N + 1, vector<int>());
for (int i = 0; i < M; i++)
{
int x, y;
cin >> x >> y;
dots[x].push_back(y);
dots[y].push_back(x);
}
for(int i = 1; i <= N; i++)
sort(dots[i].begin(), dots[i].end());
DFS(V);
cout << '\n';
fill(dot.begin(), dot.end(), false);
BFS(V);
}
후기
이 문제를 통해 DFS와 BFS를 처음 배웠다. 처음엔 이해하는데 복잡했지만 계속 함수 내 반복문, 탐색과정을 따라다니다 보니 이해하게 되었다.
이 문제를 통해 알게 된 BFS로 최근 푼 미로탐색 문제도 풀 수 있었다.
