[BOJ알고리즘, C++]#15649 N과 M(1), 깊이 정렬, DFS

[BOJ 알고리즘, C++] #1181 단어 정렬

 

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

DFS&BFS를 이용하여 주어진 자연수 범위 내에 가능한 수열의 개수 구하기

 

 

---

 

문제

 

 

그래프

문제 풀이에 앞서, 자료 구조 중 그래프에 대해서 먼저 알아보겠습니다. 자료 구조에서 그래프란, 단순히 정점과 정점들을 연결하는 간선을 하나로 모아놓은 비선형 자료 구조입니다. 객체와 객체 간의 관계를 표현하는 자료구조로 볼 수 있습니다. 그래프 자료구조를 탐색하는 방법으로, "DFS(깊이 우선 탐색)"과 "BFS(넓이 우선 탐색)"이 있습니다. 

 

DFS

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

깊이 우선 탐색이란, 하나의 정점을 기준으로 모든 정점을 차례대로 방문합니다. 탐색 과정은 한 방향으로 깊이 제한(위 그림에선 2, 5, 11, 4 등의 LEAF_NODE)에 도달할 때까지 탐색한 후, 가장 가까운 방향으로 탐색 과정을 반복합니다. 깊이 우선 탐색의 경우 두 가지 방법으로 구현 가능합니다-스택, 재귀 호출. 깊이 우선 탐색의 장점은 BFS에 비해 구현이 간단합니다. 반면에, 검색 속도는 BFS보다 느립니다. 이번 항목에서는 "재귀 호출"을 이용한 dfs 구현에 대해 알아보겠습니다.

1. Stack(스택)

2. Recursion(재귀)

 

재귀를 이용한 DFS 의사 코드

void dfs (rootNode)
{
    visit(rootNode);			 //먼저, 루트 노드 방문(가장 상단의 노드)
    rootNode.visited = true;		//방문 여부를 false -> true 
	
    for (Node n : root.adjacent)	//루트 노드의 인접 노드들의 방문여부 체크
    	if(n.visited == false)		//아직 방문 하지 않았다면, 탐색 진행
        	dfs(n);
}

재귀를 이용한 dfs 구현은 완전 탐색으로, 한 경로를 완벽하게 탐색하고 다음 경로를 탐색합니다. 이때, 필요한 두 가지 장치는 깊이 제한과 방문 여부 확인입니다. 왜냐하면, 다음 경로 탐색을 위해 마지막 노드, 즉 깊이 제한을 설정해야 하며, 마지막 노드를 방문하고 이전 노드로 돌아오는 Back Tracking 과정에서 방문했던 노드들을 재방문하는 오류를 방지하기 위해 탐색 과정에서 방문 여부를 체크해야 합니다. dfs에 대한 기본 배경 지식을 갖고, 이번 문제를 풀이해 보록 하겠습니다.

 

풀이 과정

 

1. "M"개의 원소를 갖는 수열이므로, 노드를 방문할 때마다 Count를 추가하여 M과 비교합니다.

2. dfs 재귀 호출의 기저 조건으로, Count가 M과 같다면, 수열을 출력하고 종료합니다.

3. 자연수 1부터 N까지 돌며 방문 여부를 체크합니다.

4. 방문 여부가 False라면 배열에 추가하고 다음 노드를 탐색하기 위해 "dfs(count+1)" 재귀 호출을 사용합니다.

 

코드 작성

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

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

void dfs (int cnt)
{
    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);
}