🎃 DFS 와 BFS
(https://www.acmicpc.net/problem/1260)
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 157718 55222 32454 34.435%문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4예제 출력 1
1 2 4 3
1 2 3 4예제 입력 2
5 5 3
5 4
5 2
1 2
3 4
3 1예제 출력 2
3 1 2 5 4
3 1 4 2 5예제 입력 3
1000 1 1000
999 1000예제 출력 3
1000 999
1000 999✨DFS(Depth-First-Search)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool visited[9];
vector<int> graph[9];
// node 개수만큼 vector 생성
void dfs(int x)
{
visited[x] = true;
//node 'x' visited
cout<< x << " ";
for(int i = 0 ; i < graph[x].size();i++) // 각각 인접한 노드 사이즈만큼 탐색
{
int y = graph[x][i];
if(!visited[y]) //인접 노드 방문 x라면
dfs(y); // 방문하도록 지시
}
}
🎇BFS(Breadth-First-Search)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool visited[9];
void bfs(int start)
{
queue<int> q;
q.push(start); // 첫 노드
visited[start] = true; // 방문처리
// q 가 빌때까지 반복
while(!q.empty())
{
int x= q.front();
q.pop();
cout << x << ' ';
for(int i = 0 ; i <graph[x].size(); i ++)
{
int y = graph[x][i];
if(!visited[y])
{
q.push(y);
visited[y] = true;
}
}
}
}
💎 문제 풀이
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 1001;
vector<int> graph[MAX];
bool visited[MAX] = {0,};
queue<int> q;
void dfs(int x)
{
visited[x] = true;
//방문한 노드는 방문 처리
cout << x << ' ';
for(int i = 0 ; i <graph[x].size();i++)
{
int y = graph[x][i];
if(!visited[y])
dfs(y);
}
}
void bfs(int start)
{
q.push(start);
visited[start] = true;
while(!q.empty())
{
int x = q.front();
q.pop();
cout << x << ' ';
for(int i = 0; i < graph[x].size();i ++)
{
int y= graph[x][i];
if(!visited[y])
{
q.push(y);
visited[y] = true;
}
}
}
}
int main()
{
int node;
int edge;
int starting;
cin>>node>>edge>>starting;
for(int i = 0 ; i<edge ; i++)
{
int a,b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
// graph[a][b] = 1;
// graph[b][a] = 1;
}
for(int i = 1; i<= node ; i ++)
{
sort(graph[i].begin(), graph[i].end());
}
dfs(starting);
cout<<'\n';
memset(visited,false,sizeof(visited));
bfs(starting);
return 0;
}🗝 고찰
사실 bfs, dfs 함수 구현보다, main 함수에서 input을 어떻게 받을 지를 더 고민했었다.🙄
int형 원소를 가지는 vector graph[1001]에 어떻게 입력값을 넣지?
-
각 Node 혹은 Vertex 간의 연결된 형태를 입력해야 한다.( 1번 node와 2번 node 가 연결되어있다면 1 2 가 바로 인풋일 것)
-
생각해보면 node/vertex 간 연결된 형태가 바로 edge 이고 edge의 개수만큼 각 node/vertex 연결 관계를 의미하는 정수 2개를 입력받는다. 그러면 edge의 갯수만큼 반복되는 루프 안에서 정수 2개를 각각 입력받고, 이를 graph 에 넣어주면 되겠다!
-
for(int i = 0 ; i < edge ; i ++) 내에서 cin >> a >> b 를 한 뒤, 차례대로 graph[a].push_back(b); graph[b].push_back(a); 를 실행하면 node/vertex 간 연결된 그래프가 만들어진다.
-
근데, bfs / dfs 를 돌릴 때 node/vertex를 선택하는 기준은 ' 더 번호가 작은 node/vertex' 를 먼저 탐색하라고 지정되어있다.
-
이를 어떻게 구현할까?
-
cin << a<< b 할 때, if문으로 a,b의 대소를 구분한 뒤 graph에 넣어줄까?
-
살짝 복잡할 것 같은데, 그냥 입력은 입력대로 받은 다음에 graph에 저장된 '연결 관계를 나타내는 정수' 들을 그냥 정렬해주자.
-
for(int i = 1; i <= node ; i++) 반복문 내에서 sotr(graph[i].begin(), graph[i].end()); 를 해주자.
-
그러면 graph[i] 에 저장된 원소들이 각각 내림차순으로 정렬된다.
-
bfs/dfs 과정에서 인덱스가 작은 노드를 먼저 탐색하도록 했으므로 문제에서 원하듯 작은 노드/정점을 먼저 탐색하게 구현이 된다!😆
-
놓치면 안되는 게 하나 더 있는데, 각 노드를 방문 처리할 때 bool 형 1차원 배열 visited[MAX]를 사용했다. dfs 를 먼저 돌린 뒤, 각 노드의 방문 흔적이 visited 에 남아있고, 이 상태로 bfs를 돌리면 안된다!
-
그러므로 dfs 를 돌린 뒤 visited[max]를 초기화해주어야 하는데, 이를 위해 memset을 이용했다.
-
memset 을 이용하기 위해서 cstring 을 include 하였고, memset(visited, false, sizeof(visited))로 bfs 를 돌리기 전에 방문 흔적을 초기화해주었다. (끝)
