[BOJ알고리즘, C++]#15649_N과 M(1), 깊이 우선 탐색

 

[BOJ 알고리즘, C++] #15649_N과 M(1), 깊이 우선 탐색

 

BOJ 알고리즘 문제 풀이, 15649_N과 M (1)

깊이 우선 탐색을 통해 중복이 없는 수열의 개수를 구합니다.

 

---

 

# 문제

 

# 풀이

1. 깊이 우선 탐색(DFS)

루트 노드 혹은 임의의 노드에서 시작해서 다음 분기로 넘어가기 전에, 해당 분기를 완벽하게 탐색하는 방법입니다.

 

2. DFS의 특징

1. 자기 자신을 호출하는 순환 알고리즘의 형태이다.
2. 어떤 노드를 방문했었는지 방문 여부를 반드시 검사해야 합니다.
3. 너비 우선 탐색보다 간단합니다. 
4. 검색 속도 자체는 너비 우선 탐색에 비해 느립니다.

 

3. 예제

 

1. 0번 노드를 시작으로 깊이 우선 탐색을 시작합니다.
2. 0번과 인접한 노드들을 순차적으로 순회합니다.
3. 0번과 인접한 1번 노드를 방문합니다. 이때, 다음 인접한 노드를 방문하기 전에, 1번 노드의 탐색을 먼저 완료합니다.
4. 다시, 1번 노드를 시작으로 깊이 우선 탐색을 시작합니다.
5. 위 작업을 반복하며, 4번 노드에 방문합니다.
6. 4번 노드의 인접 노드가 더 이상 없으므로, 다시 3번 노드로 돌아가 다음 인접 노드를 찾습니다.
7. 이 과정을 반복하며, 0번 정점으로 백트래킹을 진행하고, 더 이상 방문하지 않은 정점이 없을 때, 알고리즘은 끝납니다.

 

3. 의사 코드

void DFS(Node root)
{
    if (root == NULL)
        return;

    visit(root);
    root.visited = true;

    for (auto n : root.adjacents)
    {
        if (n.visited == false)
            DFS(n);
    }
}

 

Details

 

1. 루트 노드를 시작으로 DFS를 시작합니다.
2. 루트 노드의 방문 여부를 반드시 체크합니다.
3. 다음으로 인접 노드들을 방문합니다.
4. 첫 번째 인접 노드에 대한 DFS를 온전히 수행하고, 다음 인접 노드에 대한 DFS를 수행합니다!

 

# 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
int arr[9] = {
    0,
};
bool visited[9] = {
    0,
};

void dfs(int cnt)
{
    // 수열, 즉 arr의 원소 갯수가 "M"이 되면 출력합니다.
    if (cnt == M)
    {
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= N; i++)
    {
        // 방문한적이 없다면, 수열에 붙여넣고, 재귀 호출을 실행합니다.
        if (visited[i] == false)
        {
            visited[i] = true;
            arr[cnt] = i;
            dfs(cnt + 1);
            visited[i] = false;
        }
    }
}

int main()
{
    cin >> N >> M;
    dfs(0);
}

 

Details

 

• 위 코드에서 "count"를 단순히 정점의 위치라고 생각하면 간단합니다.
• 0번 정점을 시작으로, 인접 노드들을 순차적으로 방문합니다.
• 방문 여부는 Boolean 배열을  통해 확인합니다.
• 이때, 어느 한 정점의 재귀 호출이 끝나는 시점에 다음 정점으로 넘어가는 것이 주요합니다.