15650

15650번 : N과 M(2)

💡15649번 : N과 M(1) 풀이
15649번과 다른점은 순열이 아닌 조합을 구하는 문제로, 중복된 숫자를 선택해서는 안된다. 따라서 15649번의 dfs 함수에서 선택을 시작할 숫자를 따로 파라미터로 받아 for문을 돌려야 한다!

#include <iostream>
using namespace std;

int N, M;
int arr[8] = { 0, };
bool visited[8] = { 0, }; // 배열 요소 모두 0으로 초기화

void dfs(int num, int cnt) {
	if (cnt == M) {
		for (int i = 0; i < M; i++)
			cout << arr[i] << " ";
		cout << '\n';
		return;
	}
	for (int i = num; i <= N; i++) { // num부터 시작하도록 함, 조합
		if (!visited[i]) {
			visited[i] = true;
			arr[cnt] = i;
			dfs(i + 1,cnt + 1);
			visited[i] = false;
		}
	}
}

int main() {
	cin >> N >> M;

	dfs(1,0);
}

15651

15651번 : N과 M(3)

15651번은 숫자가 중복을 허용한 순열을 출력하는 문제이다. 따라서 visited를 설정할 필요가 없이 모든 경우의 수를 출력하면 된다.

#include <iostream>
using namespace std;

int N, M;
int arr[8] = { 0, };
//bool visited[8] = { 0, }; // 배열 요소 모두 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++) { 
		arr[cnt] = i;
		dfs(cnt + 1);
	}
}

int main() {
	cin >> N >> M;

	dfs(0);
}

15652

15652번 : N과 M(4)

15652번은 시작하는 숫자가 num으로 점점 증가하되 같은 숫자가 중복되어도 된다! 또한 비내림차순이다.

따라서 각 출력을 중복되는 숫자부터 하도록 dfs함수 속 dfs 파라미터를 i +1이 아닌 i로 넘겨주고, num부터 시작하는 for문을 돌리면 된다.

#include <iostream>
using namespace std;

int N, M;
int arr[8] = { 0, };
//bool visited[8] = { 0, }; // 배열 요소 모두 0으로 초기화

void dfs(int num, int cnt) {
	if (cnt == M) {
		for (int i = 0; i < M; i++)
			cout << arr[i] << " ";
		cout << '\n';
		return;
	}
	for (int i = num; i <= N; i++) { // num부터 시작하도록 함, 조합
		arr[cnt] = i;
		dfs(i, cnt + 1);
	}
}

int main() {
	cin >> N >> M;

	dfs(1, 0);
}

9663

9663번 : N-Queen

나는 체스 룰을 몰라서 당연히 퀸이 어디마다 놓여야하는지도 몰랐다. 그래서 찾아보니, 퀸을 둘러싼 모든 곳에 놓이면 안되는데, 즉 밑, 옆, 대각선에 놓이면 서로 공격할 수 있는 위치이므로 제외해야한다.

00X0 col[0]에 3번째에 퀸이 놓여있다면 col[0] = 3 이다.

🎈Check 함수

bool check(int level) {
	for (int i = 0; i < level; i++)
		if (col[i] == col[level] || abs(col[level] - col[i]) == level - i) 
			return false;
	return true;
}

level은 현재 행의 위치를 나타내는 변수이다. 지금 있는 퀸들의 위치(~col[level-1])와 놓일 퀸의 위치가 서로 어떤 관계에 있는 지, 지금 위치에 놓아도 되는지 확인 하는 함수이다. 같은 col이면 바로 아래에 위치한다는 뜻이므로 false이고, col[i]가 의미하는 것이 X좌표, i가 의미하는것이 Y좌표이므로 차이가 일정하다면 대각선에 있다고 볼 수 있다. 그에 따라 false를 부여한다.

🎈nqueen 함수

void nqueen(int x) {
	if (x == N)
		result++;
	else {
		for (int i = 0; i < N; i++) {
			col[x] = i;
			if (check(x)) // 유효하면 다음행 퀸 배치, 아니면 다른위치 퀸 변경
				nqueen(x + 1);
		}
	}
}

확인하고 있는 행을 순서대로 하나씩 넣어보며 확인한다. check함수를 불러와 그 자리가 유효한지를 확인하고, 유효하다면 다음 행으로 넘어가는 방식이다.

#include <iostream>
using namespace std;

int col[15];
int N, result = 0;

bool check(int level) {
	for (int i = 0; i < level; i++)
		if (col[i] == col[level] || abs(col[level] - col[i]) == level - i) // 차이가 일정하면 대각선
			return false;
	return true;
}

void nqueen(int x) {
	if (x == N)
		result++;
	else {
		for (int i = 0; i < N; i++) {
			col[x] = i;
			if (check(x)) // 유효하면 다음행 퀸 배치, 아니면 다른위치 퀸 변경
				nqueen(x + 1);
		}
	}
}

int main() {
	cin >> N;
	nqueen(0);
	cout << result;
}