DFS
깊이 우선 탐색
그래프를 지정한 노드에서 시작해서 각 분기를 가능한 한 최대한 탐색하고 다음 분기로 넘어간다.
방식을 순서로 설명하면,
1. 지정한 노드에서 현재 노드를 방문하고 방문한 것으로 표시한다.
2. 인접한 노드 중 방문하지 않은 노드를 선택한다. 방문하지 않은 노드가 많다면 임의로 선택한다.
3. 선택된 인접 노드에 대해 1번과 2번을 반복한다.
4. 더 이상 인접 노드 중에 방문하지 않은 노드가 없다면, 이전 노드로 돌아가 2번을 반복한다.
5. 모든 노드를 방문하거나 원하는 노드를 찾으면 종료.
BFS
너비 우선 탐색
그래프에서 가장 가까운 노드부터 탐색하여, 현재 깊이에서 모든 노드를 검사하고 다음 깊이로 이동한다.
보통 큐를 사용하는 알고리즘이다.
1. 시작 노드를 큐에 집어 넣는다.
2. 큐에 넣은 노드를 방문 처리한다.
3. 큐에 넣은 노드를 꺼낸다.
4. 이후 인접 노드 중 방문하지 않은 모든 노드를 큐에 넣는다.
5. 큐가 빌 때까지 2번과 3번을 반복한다.
6. 모든 노드를 방문하거나 원하는 노드를 찾으면 종료.
백준 1260번: DFS와 BFS
문제 - 그래프를 DFS와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하라. 단, 방문할 수 있는 정점이 여러 개인 경우에는 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력 - 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력 - 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
풀이
우선, 사용할 헤더이다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>당연하게도, BFS를 위한 queue와 방문 노드를 표시하기 위한 vector가 필요하다. DFS를 스택 구조로 구현할 것이라면 stack도 포함해야 한다.
DFS와 BFS의 입력은 시작 노드이다. 이를 기반으로, 위에서 설명한 순서대로 코드를 구현한다.
DFS
0. 알고리즘에 사용할 컨테이너가 있어야 한다. visited는 bool로 방문을 했는지 표시하고, graph는 vector 안의 vector 형태로 구현하여 각 노드에 연결된 노드를 관리할 수 있도록 한다. (벡터의 배열이라 생각하면 편리하다.)
std::vector<std::vector<int>> graph;
std::vector<bool> visited;
1. 현재 노드 방문
visited[x] = true;
2. 인접한 노드 중 방문하지 않은 노드를 선택
for (int neighbor : graph[x])
{
if (!visited[neighbor])
{
3. 선택된 인접 노드에 대해 1번과 2번을 반복, 동시에 재귀 호출을 통해 4번까지 해결한다.
for (int neighbor : graph[x])
{
if (!visited[neighbor])
{
DFS(neighbor);
}
}
5. 모든 노드를 방문하면 종료.
이를 전부 구현한 함수로 확인하면 다음과 같다.
void DFS(int x)
{
// 1. 현재 노드 방문
visited[x] = true;
// 2. 인접한 노드 중 방문하지 않은 노드를 선택
for (int neighbor : graph[x])
{
if (!visited[neighbor])
{
// 3. 선택된 인접 노드에 대해 1번과 2번을 반복
// 재귀 호출을 통해 4번까지 행함
// 노드를 찾는 행동이 없으므로 모든 노드 방문시 종료
DFS(neighbor);
}
}
}
BFS
0. BFS를 구현하기 위한 queue가 존재해야 한다.
std::queue<int> q;
1. 시작 노드를 큐에 집어 넣는다.
q.push(x);
2. 큐에 넣은 노드를 방문 처리한다.
visited[x] = true;
3. 큐에 넣은 노드를 꺼낸다. 이때 모든 노드를 방문해야 하므로, 큐가 완전히 빌 때까지 이후의 코드를 반복해야 한다.
while (!q.empty()) {
q.pop();
4. 이후 인접 노드 중 방문하지 않은 모든 노드를 큐에 넣는다. 이때, for문으로 시작 노드의 인접 노드를 전부 알아와야 하기 때문에, 시작 노드를 가지고 있어야 한다.
// 현재 노드를 식별하기 위한 변수
int i = q.front();
q.pop();
for (int neighbor : graph[i])
{
if (!visited[neighbor])
{
// 이 코드에서는 방문 처리를 함과 동시에 큐에 노드를 넣는다.
// 이후 인접 노드를 전부 큐에 넣었다면, 다시 위로 올라가 큐가 빌 때까지 반복한다.
visited[neighbor] = true;
q.push(neighbor);
}
}5. 큐가 빌 때까지 2번과 3번을 반복한다. 이때, 2번의 경우는 4번을 실행하면서 큐에 노드를 넣으며 동시에 진행되므로, 따로 더 처리할 필요가 없다.
6. 모든 노드를 방문하면 완료.
이를 전부 구현한 함수로 확인하면 다음과 같다.
void BFS(int x)
{
std::queue<int> q;
// 1. 시작 노드를 큐에 집어 넣는다.
q.push(x);
// 2. 큐에 넣은 노드를 방문 처리한다.
visited[x] = true;
// 큐에서 모든 노드를 꺼냈다면 종료 (전부 꺼낸 이후 새롭게 push가 없다면 종료)
while (!q.empty()) {
// 현재 노드를 식별하기 위한 변수
int i = q.front();
// 3. 큐에 넣은 노드를 꺼낸다.
q.pop();
// 4. 이후 인접 노드 중 방문하지 않은 모든 노드를 큐에 넣는다.
for (int neighbor : graph[i])
{
if (!visited[neighbor])
{
// 이 코드에서는 방문 처리를 함과 동시에 큐에 노드를 넣는다.
// 이후 인접 노드를 전부 큐에 넣었다면, 다시 위로 올라가 큐가 빌 때까지 반복한다.
visited[neighbor] = true;
q.push(neighbor);
}
}
// 5. 큐가 빌 때까지 2번과 3번을 반복한다.
}
}
이제, 각 함수도 구현했으니 문제를 풀어보자.
문제에 나와있는 정보에 따르면, "단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다." 라는 문장이 있다.
이 조건을 달성하기 위해서 나는 각 graph에 저장된 노드의 인접 노드를 정렬하면 된다고 판단하였다.
std::sort(graph[x].begin(), graph[x].end());즉, 알고리즘 헤더에 포함되어 있는 sort 함수를 활용하여 graph의 각 노드에 대한 인접 노드 정보를 정렬하고, 이후에 알고리즘을 수행하면 된다는 것이다.
이 코드를 포함한 수정된 함수의 전문은 다음과 같다. (출력을 위한 코드도 포함되어 수정되었다.)
void DFS(int x)
{
// 1. 현재 노드 방문
visited[x] = true;
std::cout << x << " ";
// 인접 노드 정렬
std::sort(graph[x].begin(), graph[x].end());
// 2. 인접한 노드 중 방문하지 않은 노드를 선택
for (int neighbor : graph[x])
{
if (!visited[neighbor])
{
// 3. 선택된 인접 노드에 대해 1번과 2번을 반복
// 재귀 호출을 통해 4번까지 행함
// 노드를 찾는 행동이 없으므로 모든 노드 방문시 종료
DFS(neighbor);
}
}
}
void BFS(int x)
{
std::queue<int> q;
// 1. 시작 노드를 큐에 집어 넣는다.
q.push(x);
// 2. 큐에 넣은 노드를 방문 처리한다.
visited[x] = true;
// 큐에서 모든 노드를 꺼냈다면 종료 (전부 꺼낸 이후 새롭게 push가 없다면 종료)
while (!q.empty()) {
// 현재 노드를 식별하기 위한 변수
int i = q.front();
std::cout << i << " ";
// 3. 큐에 넣은 노드를 꺼낸다.
q.pop();
// 인접 노드 정렬
std::sort(graph[i].begin(), graph[i].end());
// 4. 이후 인접 노드 중 방문하지 않은 모든 노드를 큐에 넣는다.
for (int neighbor : graph[i])
{
if (!visited[neighbor])
{
// 이 코드에서는 방문 처리를 함과 동시에 큐에 노드를 넣는다.
// 이후 인접 노드를 전부 큐에 넣었다면, 다시 위로 올라가 큐가 빌 때까지 반복한다.
visited[neighbor] = true;
q.push(neighbor);
}
}
// 5. 큐가 빌 때까지 2번과 3번을 반복한다.
}
}그리고, main에서 이 수정된 함수들을 호출하면 될 것이다.
입력은 N, M, V와 M의 개수만큼 노드와 인접 노드가 전달된다. 필요한 변수는 총 5개.
그러나 이후 인접 노드를 입력 받기 이전에, graph에 값을 넣기 위해서 vector의 크기를 초기화할 필요가 있다.
reserve라는 함수와 resize라는 함수가 있는데, 여기에서 나는 visited를 크기 조정과 동시에 모든 값을 false로 변환하고 싶어 resize를 사용하였다.
int N, M, V;
std::cin >> N >> M >> V;
graph.resize(N + 1);
visited.resize(N + 1, false);
그 다음은, M의 수 만큼 인접 노드에 대한 정보를 받아오면 된다. 두개씩 입력되므로 변수를 두개 사용한다.
for (int i = 0; i < M; ++i)
{
int u, v;
std::cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
그 다음엔 간단하다. 단순히 DFS를 호출하고, visited를 assign 함수를 통해 다시 false로 전부 변환한 뒤 다시 BFS를 호출하면 된다.
DFS(V);
std::cout << std::endl;
visited.assign(N + 1, false);
BFS(V);
이를 모두 포함한 전체 코드의 전문은 다음과 같다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
const int MAX_NUM = 1001;
std::vector<std::vector<int>> graph;
std::vector<bool> visited;
void DFS(int x)
{
// 1. 현재 노드 방문
visited[x] = true;
std::cout << x << " ";
// 인접 노드 정렬
std::sort(graph[x].begin(), graph[x].end());
// 2. 인접한 노드 중 방문하지 않은 노드를 선택
for (int neighbor : graph[x])
{
if (!visited[neighbor])
{
// 3. 선택된 인접 노드에 대해 1번과 2번을 반복
// 재귀 호출을 통해 4번까지 행함
// 노드를 찾는 행동이 없으므로 모든 노드 방문시 종료
DFS(neighbor);
}
}
}
void BFS(int x)
{
std::queue<int> q;
// 1. 시작 노드를 큐에 집어 넣는다.
q.push(x);
// 2. 큐에 넣은 노드를 방문 처리한다.
visited[x] = true;
// 큐에서 모든 노드를 꺼냈다면 종료 (전부 꺼낸 이후 새롭게 push가 없다면 종료)
while (!q.empty()) {
// 현재 노드를 식별하기 위한 변수
int i = q.front();
std::cout << i << " ";
// 3. 큐에 넣은 노드를 꺼낸다.
q.pop();
// 인접 노드 정렬
std::sort(graph[i].begin(), graph[i].end());
// 4. 이후 인접 노드 중 방문하지 않은 모든 노드를 큐에 넣는다.
for (int neighbor : graph[i])
{
if (!visited[neighbor])
{
// 이 코드에서는 방문 처리를 함과 동시에 큐에 노드를 넣는다.
// 이후 인접 노드를 전부 큐에 넣었다면, 다시 위로 올라가 큐가 빌 때까지 반복한다.
visited[neighbor] = true;
q.push(neighbor);
}
}
// 5. 큐가 빌 때까지 2번과 3번을 반복한다.
}
}
int main()
{
int N, M, V;
std::cin >> N >> M >> V;
graph.resize(N + 1);
visited.resize(N + 1, false);
for (int i = 0; i < M; ++i)
{
int u, v;
std::cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
DFS(V);
std::cout << std::endl;
visited.assign(N + 1, false);
BFS(V);
}그대로 백준에 제출해보면
정답이라는 결과를 얻을 수 있다.
코드 길이는 주석을 제거하면 줄어들 것이다.
사실 조금 더 최적화 할 수 있을 것이라 생각하지만, 우선은 넘어가도록 하고 이후에 진행하는 DFS와 BFS 관련 문제에서 가능한 한 최적화를 하여 코드를 짜보겠다.
'알고리즘' 카테고리의 다른 글
| 프로그래머스 C++ 문제 풀이 - 여행경로(DFS/BFS) (0) | 2024.06.12 |
|---|---|
| 프로그래머스 C++ 문제 풀이 - 단어 변환(BFS/DFS) (0) | 2024.06.08 |
| 섬 연결하기 C++ 풀이 (0) | 2024.05.27 |