15649 - N과 M(1)

문제

코드

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a[10];
bool visited[10];

void choice(int cnt){
	if(cnt == m){
		for(int i = 0; i < m; i++){
			cout << a[i] << ' ';
		}
		cout << '\n';
	}
	
	for(int i = 1; i <= n; i++){
		if(!visited[i]){
			visited[i] = true;
			a[cnt] = i;
			choice(cnt + 1);
			visited[i] = false;
		}
	}
}

int main(){
	cin >> n >> m;
	choice(0);
}

풀이

중복을 허용하지 않고 m를 뽑는 경우를 구해야한다.
진짜 간단히 1부터 2, 3, 4 이런식으로 하나씩 뽑아내면 된다.
본인만 체크해두고 나머지랑 짝 지어서 뽑아내면 된다.
choice 함수를 적고도 많이 헷갈렸는데 for문의 진행방식에 대해 좀 더 자세히 설명하려고 한다.
i가 1부터 진행된다.
1. visited가 false이면 true로 바꾸고 출력할 배열인 a에 집어 넣는다.
2. 다시 재귀로 choice 함수를 불러 1이 체크된 상태를 넘겨둔다.
3. i가 2가 되며 visited를 true로 바꾸고 출력할 배열인 a에 집어 넣는다.
4. 다시 재귀로 choice 함수를 불러 2이 체크된 상태를 넘겨둔다.
n까지 진행된다면 시작이 1,2,3 ... n이고 cnt가 0인 여러 개의 출력할 배열이 만들어 진다.
이렇게 만들어진 배열이 각각 다시 choice 함수를 진행하게 된다.
즉 1로 시작하는 수부터 진행한다.
1이 visited 되어 있기 때문에 1,2를 담고 cnt늘리고 choice 재귀 실행
1,3을 담고 같은 행위 반복 이렇게 반복하면 cnt가 1인 1,2 1,3 1,4 2,1 2,2와 같은 출력할 배열이 만들어진다.
그러면 원하는 값에 맞춰서 출력을 할 수 있다.

결과

후기

헷갈렸던 부분이 백트래킹이 어떤 순서나 움직임을 갖는지였는데 하나씩 디버그 찍어보며 하니 어떤 식으로 진행되는지 알 수 있었다.
한 4-5일 전에 풀었는데 방식에 대해 고민하다가 드디어 깨닫고 블로그에 남긴다.
결과를 보면 withoutreturing 오류가 떠있는데 함수의 출력이 없을 때 나오는 오류라고 한다. 실수로 choice 함수의 반환형을 int로 설정해둬서 생긴 오류였다.
n과 m 시리즈를 계속 풀어보며 기본적 개념에 대해 조금 더 공부해야겠다.