[백준/C++] 15649번 : N과 M(1) (백트래킹 연습)

N과 M (1) 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 

3 1

 

예제 출력 1 

1
2
3

예제 입력 2 

4 2

예제 출력 2 

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3 

4 4

예제 출력 3

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

---

💡 백트래킹 (Backtracking)

백트래킹이란, 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말한다.

백트래킹 문제는 DFS 알고리즘을 사용해서 풀이하기 때문에 DFS 방식에서 조금 변형된 DFS의 다른 유형이라고 볼 수 있다.

 

깊이 우선 탐색인 DFS는 가능한 모든 경로(후보)를 탐색하기 때문에 불필요할 것 같은 경로를 사전에 차단하는 등의 행동을 할 수 없다.

따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리하기 어렵다.

 

이러한 경우 백트래킹을 이용하여 해를 찾아가는 도중, 지금의 해가 될 것 같지 않다면 그 경로를 더이상 따라가지 않고 되돌아가면 된다.

 

백준에서 N과 M은 백트래킹의 대표 문제이다.

주어진 N까지의 수들을 M개의 수열로 출력하며 중복없는 조건을 맞추어야 한다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N, M;
int arr[9];
bool visit[9];

void DFS(int num)
{
	if (num == M)
	{
		for (int i = 0; i < M; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= N; i++)
	{
		if (!visit[i])
		{
			visit[i] = true;
			arr[num] = i;
			DFS(num + 1);
			visit[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	DFS(0);

	return 0;
}

 

 

먼저 0번째 순서부터 DFS 함수를 시작하였다.

DFS의 깊이에 해당하는 num 매개변수가 M값과 같다면, 즉 M개의 수열 순서까지 도달했다면 현재 수열이 담긴 배열 arr을 차례로 출력한 뒤 return 하며 함수를 빠져나오도록 하였다.

 

M개 수열에 도달하지 못했다면 i = 1부터 N까지의 방문여부를 확인하면서, 아직 수열을 담는 배열(arr)에 들어가지 않은 숫자라면 방문 true 처리를 한 뒤, arr 배열에 해당 수를 추가하였다.

이후, DFS(num + 1)을 호출하여 다음 배열 인덱스로 들어올 숫자를 찾아 나선다.

계속해서 인덱스가 증가하다가 M만큼의 배열을 다 채우면 DFS를 순서대로 탈출하면서 visit 배열을 false로 다시 초기화 시킨다.

 

수열을 하나만 출력하는 것이 아니라 i = 1부터 N까지의 모든 수열을 출력해야 하므로 visit 변수를 다시 false로 정리하는 것이다.

 

arr 배열은 따로 초기화하지 않아도 재초기화 되며 정리된다.

 

백트래킹 문제를 처음 풀어봐서 DFS로 푸는건지도 몰랐다..ㅎㅎ

그래도 생각보다 재밌게 풀이할 수 있었다.

---

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

https://chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제