https://www.acmicpc.net/problemset?sort=ac_desc&algo=7
문제 - 1 페이지
www.acmicpc.net
이문제의 경우 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS)의 차이를 알기에는 딱인 문제 였다.
일단 BFS의 경우 재귀함수를 사용하지 않고 풀어 보았다
현재 이렇게 입력값을 주었을 경우 BFS는 기준점을 기준으로 선 1개를 통해 연결 된 애들 선 2개를 통해 연결된 애들
이런식으로 단계를 나눠준다
이렇게 생각을 하거나 아니면
DFS의 경우에는 또 다르게 생각해주어야한다 비슷하게 생각해보자면 최대한 길게 선을 그어서 모든 정점을 방문하는 방법이라고 생각한다 단 다시 되돌아가기는 내가 왔던 점으로만 돌아 갈수 있다 또한 만약에 이때 다른 경로가 아직 방문되지 않았고 내가 간적 없는 정점이라면 그곳으로 간다. 즉 최대한 길게 갈려고 한다고 생각하면 된다.
다르게 생각하면 부모를 기준으로 내 첫째 자식의 후손들 까지 갔다가 2째 자식의 후손들 까지 쭉보고 나머지 자식들 순으로 그 자식들의 후손들까지 쭉 보는거라고 생각하면된다
이런식으로 기준점을 1로 두고 1과 선 한개로 연결된 애들과 선을 2개로 해서 갈수 있는 애들을 나눠서 생각해줄수 있다
단 밑에 그림처럼 생각할시에는 2번째 단계에서 이미 4를 방문했으므로 3단계에 있는 4에는 방문을 할 필요가 없다고 생각해주면 된다.
일단 전체 코드를 첨부후 부분 부분 설명하도록 하겠다.
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<memory.h>
using namespace std;
vector <int> vertex[10002];
vector <int> resultofDfs;
vector <int> resultofBfs;
int vertexnum;
bool visited[1001] = { false, };
//dfs 함수
void dfs(int start) {
resultofDfs.push_back(start);
visited[start] = 1;
for (int i = 0; i < vertex[start].size(); i++) {
if (visited[vertex[start][i]] == true){
continue;
}
dfs(vertex[start][i]);
}
}
int main() {
queue<int> Bfsqueue;
int edgenum;
int startvertex;
int startvertexforDfs;
int inputvertex;
int inputedge;
cin >> vertexnum;
cin >> edgenum;
cin >> startvertex;
startvertexforDfs = startvertex;
resultofBfs.push_back(startvertex);
for (int i = 0; i < edgenum; i++) {
cin >> inputvertex >> inputedge;
vertex[inputvertex].push_back(inputedge);
vertex[inputedge].push_back(inputvertex);
}
//작은것부터 나와야하니까 정렬해준다
for (int i = 1; i <= edgenum; i++) {
sort(vertex[i].begin(), vertex[i].end());
}
//DFS
dfs(startvertexforDfs);
for (int i = 0; i < resultofDfs.size(); i++) {
cout << resultofDfs[i] << ' ';
}
cout << endl;
// 배열 재사용 위해 초기화
memset(visited, 0, sizeof(visited));
//BFS
visited[startvertex] = true;
for (int i = 0; i < vertexnum; i++) {
int sizeofvertex = vertex[startvertex].size();
for (int j = 0; j < sizeofvertex; j++) {
if (visited[vertex[startvertex][j]] == false) {
visited[vertex[startvertex][j]] = true;
Bfsqueue.push(vertex[startvertex][j]);
resultofBfs.push_back(vertex[startvertex][j]);
}
}
if (Bfsqueue.empty()) {
break;
}
startvertex = Bfsqueue.front();
Bfsqueue.pop();
}
for (int i = 0; i < resultofBfs.size(); i++) {
cout << resultofBfs[i] << ' ';
}
}맨처음 각각의 정점들이 누구랑 연결되어 있는지를 vector형태로 넣어 줄 수 있도록 만들어 주었다
만약
이런 식으로 입력받아지면
vector[1] 에 2,3,4
vecotr[2] 에 1,4
vector[3] 에 1,4
가 들어가게 된다 즉 내가 다른 누군가와 연결되었는지를 입력해주게 된다
그다음 각 정점이 방문되었는지를 확인해주는 visited 배열을 만들어 주었다
void dfs(int start) {
resultofDfs.push_back(start);
visited[start] = 1;
for (int i = 0; i < vertex[start].size(); i++) {
if (visited[vertex[start][i]] == true){
continue;
}
dfs(vertex[start][i]);
}
}이 부분의 경우
일단 내가 들어온 곳을 방문 했다고 마크 한다
그후 for문 첫번째 조건에서 내가 아무하고 도 연결안되어있으면 for문을 돌지 않는다 그래서 더이상 가지않고 함수를
return하고 재귀적으로 call하기 이전의 함수가 다시 경로를 찾는다.
혹은 내가 만약에 방문할 수 있는 경로가 있더라도 그곳이 방문됬었다면 방문하지 않고 다른 경로를 찾는다.
BFS의 코드는 재귀가 아니라 반복문으로 작성하였다.
visited[startvertex] = true;
for (int i = 0; i < vertexnum; i++) {
int sizeofvertex = vertex[startvertex].size();
for (int j = 0; j < sizeofvertex; j++) {
if (visited[vertex[startvertex][j]] == false) {
visited[vertex[startvertex][j]] = true;
Bfsqueue.push(vertex[startvertex][j]);
resultofBfs.push_back(vertex[startvertex][j]);
}
}
if (Bfsqueue.empty()) {
break;
}
startvertex = Bfsqueue.front();
Bfsqueue.pop();
}이 부분의 경우 일단 시작점은 무조건 방문한거니 true로 마크해준다
그 이후에 나랑 연결된 애들중에 방문되지 않은애들을 큐에다가 넣어 준다 resultofBFS 는 큐는 pop을 이용해서 정보를 빼고 더하기 때문에 vector에다가 방문하는 지점을 저장해주기 위해 만들어 놓은것이다 큐에 있는 것들을 pop해주면서 pop되는 애들의 자식들도 queue에다가 넣어준다 이것을 반복해서 같은대의 자식들이 계속 큐에 넣어져서 접근한다 이후에 큐가 비게되면 모두 방문한거가 된다 순서를 보자면
5 5 3
5 4
5 2
1 2
3 4
3 1처음 큐 3-> 1,4->2-5이런식으로 root로 부터 몇개의 선으로 갈수 있는지에 따라 level이 나누어 진다
이로서 큐를 이용해서 작성해주면 편하게 작성할 수 있다