백준 15649번 : N과 M(1)

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

문제읽기

길이가 M인 수열. 1부터 N까지의 자연수를 나열하고, 출력은 공백으로 구분. 증가하는 것은 사전 순으로!

코드

#include<iostream>
using namespace std;

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

void solve(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]) {
			visited[i] = true;
			arr[cnt] = i;
			solve(cnt + 1);
			visited[i] = false;
		}
	}
	return;
}

int main() {
	cin >> N >> M;
	int cnt = 0;
	solve(cnt);
	return 0;
}

분석

약간 그런 느낌이다. 기억은 나는데 정확하게 뭔지는 모르는 것... 암튼간에 dfs로 접근했다.

먼저 base case이다. 길이가 M과 같아진다면 모든 배열을 print하고 return시켜 버린다.

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

두번째로 general case이다.
우선 방문하지 않은 숫자라면 진행한다. 중복을 회피해야 하기 때문이다. 중복된 숫자가 아니라면 방문을 표시하고 arr에 해당 숫자를 넣어준다. 그러고 dfs 탐색을 시작한다. 재귀 특성을 이용하고 나면 방문 표시를 지워줌으로써 1*** 탐색 이후 2*** 탐색에 문제가 없도록 한다.

for (int i = 1; i <= N; i++) {
	if (!visited[i]) {
		visited[i] = true;
		arr[cnt] = i;
		solve(cnt + 1);
		visited[i] = false;
	}
}