1260. DFS와 BFS
문제링크 : https://www.acmicpc.net/problem/1260
코딩테스트 준비하던 와중에 이미 풀어봤던 문제이기는 했는데, 회사에 다닌다고 오랫동안 코딩테스트를 놓고 공부를 안했더니 기본적인 DFS BFS도 까먹은 상태여서 가장 먼저 잡았던 문제다.
DFS BFS는 학부 시절 알고리즘 과목에도 나올 만큼 기본적인 알고리즘이므로 이번 기회에 확실히 개념을 잡고 가는 게 좋겠다.
# DFS와 BFS 개념
DFS와 BFS 모두 그래프를 탐색하는 알고리즘이다.
여기에서 그래프는 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조를 말한다.
'그래프를 탐색한다'의 의미는 하나의 정점으로부터 시작해서 순서대로 모든 정점들을 한 번씩 방문한다는 의미이다.
- DFS
깊이 우선 탐색(DFS, Depth-First Search)은 말 그대로 그래프를 탐색하는 순서를 정할 때 최대한 깊이 내려간 다음에 더 이상 깊이 갈 수 없는 상황일 경우에만 옆으로 이동한다.
루트 노드(혹은, 탐색을 최초로 시작하는 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.
쉽게 설명하면, 미로에서 탈출하고자 할 때 한 방향으로 막힌 길이 나올 때까지 계속해서 가다가 막힌 길이 나오면 갈 수 있는 방향 중에 하나를 선택해서 그제서야 다른 방향으로 이동하는 경우를 예로 들 수 있다.
- BFS
너비 우선 탐색(BFS, Breadth-First Search)은 DFS와 달리 최대한 넓고 얕게 이동한 다음 더 이상 갈 수 없을 때 아래로 이동하는 방식을 말한다.
루트 노드(혹은, 탐색을 최초로 시작하는 노드)에서 시작해서 최대한 인접한 노드를 먼저 탐색하는 알고리즘인데, 가까운 정점부터 방문하고 멀리 있는 정점을 방문하기 때문에 주로 어떤 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 사용한다.
# 문제 풀이
우선 N, M, V와 간선에 대한 입력을 받을 때 vector connect_v[1001]을 선언해서 각 점에서 접근할 수 있는 점들을 DFS와 BFS에서 접근하기 쉽도록 구현했다.
예시)
정점 1번에서 방문할 수 있는 정점이 2,3,4가 있다면 connect_v[1]에는 2,3,4가 저장되어 있는 방식으로 구현함
이 때, 입력받는 간선의 순서가 위의 예시처럼 2,3,4가 아니라 4,3,2 이런 식이라면 4,3,2 순으로 방문할 수 있는 위험이 있기 때문에 (문제에서는 방문할 수 있는 점이 여러개인 경우 정점의 번호가 작은 것부터 방문하라는 조건이 있었음) algorithm 헤더를 추가하여 오름차순으로 정렬(sort) 해주는 작업이 필요했다.
DFS는 재귀함수를 사용해서 ch(check) 배열에 정점을 방문할 때마다 ch[v]을 1로 체크하여 방문했음을 표시해주고, 그 정점에서 방문할 수 있는 점 중에 방문하지 않은 점부터 순서대로 방문하도록 했다.
일차원 배열 초기화를 위해 cstring 헤더를 추가하여 memset(ch, 0, sizeof(ch)로 0으로 초기화했다.
memset(초기화할 배열의 이름, 0, 배열의 크기)
이 때, -1로 초기화하고 싶으면 0을 -1로 바꾸면 됨
BFS는 첫 정점을 큐에 넣고 그 정점에서 접근할 수 있고, 아직 방문되지 않은 점들을 큐에 넣는 방식으로 구현했다.
이 구현에서 주의점은 큐에 넣기 전에 넣을 정점을 방문처리 (ch[정점] = 1) 해주지 않으면 그 정점이 큐에 여러 번 들어가게 되어 여러 번 방문될 위험이 있기 때문에 큐에 넣기 전에 방문 처리가 필수다.
// 1260. DFS와 BFS
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M, V;
int ch[1001];
struct edge {
int v1;
int v2;
};
vector<int> connect_v[1001];
vector<int> visit_dfs;
vector<int> visit_bfs;
void DFS(int v) {
ch[v] = 1;
visit_dfs.push_back(v);
for (int i = 0; i < connect_v[v].size(); i++) {
if (ch[connect_v[v][i]] == 1) continue;
DFS(connect_v[v][i]);
}
}
int main() {
cin >> N >> M >> V;
for (int i = 1; i <= M; i++) {
int v1, v2;
cin >> v1 >> v2;
connect_v[v1].push_back(v2);
connect_v[v2].push_back(v1);
}
for (int i = 1; i <= N; i++) {
sort(connect_v[i].begin(), connect_v[i].end());
}
DFS(V);
memset(ch, 0, sizeof(ch));
queue<int> q;
q.push(V);
while (!q.empty()) {
int cur_v = q.front();
ch[cur_v] = 1;
visit_bfs.push_back(cur_v);
q.pop();
for (int i = 0; i < connect_v[cur_v].size(); i++) {
if (ch[connect_v[cur_v][i]] == 1) continue;
ch[connect_v[cur_v][i]] = 1;
q.push(connect_v[cur_v][i]);
}
}
for (int i = 0; i < visit_dfs.size(); i++) {
cout << visit_dfs[i] << ' ';
}
cout << endl;
for (int i = 0; i < visit_bfs.size(); i++) {
cout << visit_bfs[i] << ' ';
}
}# 개선점 및 참고할 점
다른 사람들의 풀이를 보니 간선을 입력받을 때 나처럼 벡터가 아니라 인접행렬을 구현했었다. 간선의 개수가 적은 게 아니라 많을 경우, 인접행렬이 메모리 공간 효율을 생각했을 때 더 효율적일 것이라는 생각이 들었다.
이 문제의 경우에는 점의 개수가 최대 1000개이기 때문에 인접행렬로 구현해도 메모리 공간 제한을 넘지 않을 것이기에 차후에 비슷한 문제를 풀 때는 이 부분도 고려해야만 하겠다.
설명 참고 : https://devuna.tistory.com/32
