[C++] 백준 15649 문제 해설

15649번: N과 M (1)

이 문제는 n 과 m 을 입력받아.자연수 $1 \sim N$ 까지의 자연수 중 중복 없이 이뤄진 수열 $M$ 개를 도출한다.

 

설명이 조금 애매한데, 예제를 보면 쉽게 이해가 가능하다.

엄밀히 말해 $1 \sim N$ 까지의 자연수 중 $M$ 개로 이뤄진 수열의 '모든 조합' 을 찾는 것이다.

#include <iostream>

int n, m;
int arr[9] = { 0, };
bool visited[9] = { 0, };

void DFS(int cnt)
{
	// cnt 와 m 간의 1의 갭을 주므로서 자연스럽게 반복문 최고치에
	// 도달했을 때 arr 내용이 출력됨.
	if (cnt == m)
	{
		for (int i = 0; i < m; ++i)
			std::cout << arr[i] << ' ';
		std::cout << '\n';
		return;
	}

	// 1 부터 n 반복문, 내부 재귀함수서 모든 경우의 수를 계산.
	for (int i = 1; i <= n; ++i)
	{
		// 숫자 i 가 아직 선택되지 않았다면
		if (visited[i] == false)
		{
			visited[i] = true;  // 숫자 i 를 선택했다고 표시
			arr[cnt] = i;       // arr[] 의 cnt 위치에 숫자 i 를 저장
			DFS(cnt + 1);       // 다음 숫자를 선택하기 위해 재귀적으로 호출
			visited[i] = false; // 현재 선택한 숫자 i 를 선택하지 않았다고 표시, (이러면 다음 순열 생성 시 이 숫자를 다시 사용 가능)
		}
	}
}

int main()
{
	std::cin >> n >> m;
	DFS(0);
}

해당 코드는 나도 여러 글을 보며 찾아본 내용을 기반으로 작성한 것이다.

사실 좀 귀찮아서 굳이 짜려고 시도하지 않고,

답지를 보면서 이해하려고 시도했는데 직접 짜볼 것 그랬다.

 

답 코드만 보고도 이해하는데 꽤 난해하였다.

재귀함수를 기반으로 한 로직이 꽤 까다롭게 작성되어 있다.

 

아랫쪽의 for 문서 visited[i] 를 설정하게 되어있는데,

visited[i] 는 같은 수를 arr 에 삽입하였는지, 하지 않았는지를 체크하기 위한 용도이다.

 

DFS() 재귀 부분은 직접 체크해서 왜 이렇게 돌아가는지 확인해 보는것이 좋을듯 하다. (상당히 복잡한 로직이다)

대충 그려본 3 3 입력시, 1-3-2 까지 출력되는 로직.

 

중요한 점으로 결국 cnt 는 현재 배열에 몇개의 수가 들어있는지 파악하는 역할을 수행하며,

visited 는 방문 여부만 체크하는 형식이다.

 

여기서 visited 를 통해 '이미 삽입된' 숫자는 배제하고, 나머지 숫자를 '사전 순서 (1 ~ 9)' 대로 삽입할 수 있으며,

재귀 형식을 통해 '이미 들어갔던 조합' 이 아닌 다른 조합을 삽입하도록 한다.

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

최종적으로 재귀 구문상 arr 에 모든 수가 하나씩 들어간 뒤에야 출력 구문을 거친다.

여기서 cnt 와 m 간의 차이를 1 둠으로서 자연스럽게 출력되도록 한 것은 묘미이다.

 

약간의 쓸모없는 연산이 포함되어 있긴 하지만, 큰 무리 없이 돌아가는 구조라고 생각한다.

 

추가로

재귀함수는 개인적으로 매우 싫어하나

DFS 알고리즘 특성상 재귀함수 구현이 적절하다.

이러한 재귀함수를 디버깅 할때는 Call Stack 도구로 깊이를 확인하는 방식이 좋다.