글 읽기 - 조금 더 효율적으로 풀 수 있는 방법이 있을까요?

jemin9312 5년 전 0

이차원 배열을 이용해 좌표처럼 인식하고 백트래킹으로 해결했는데 조금 찝찝한 느낌이 있어서 질문드립니다.

이차원 배열을 사용하지 않고 풀수있는 방법이 있을까요?

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

bool check[15][15];

int n;
int cnt = 0;

bool go(int row, int col) {

	for (int i = 0; i < n; i++) {
		if (i == row)
			continue;
		if (check[i][col])
			return false;
	}

	for (int i = 1; i < n; i++) {
		if (row - i >= 0 && col - i >= 0)
			if (check[row - i][col - i])
				return false;
	}

	for (int i = 1; i < n; i++) {
		if (row - i >= 0 && col + i < n)
			if (check[row - i][col + i])
				return false;
	}

	return true;

}


void dfs(int row) {

	if (row == n) {
		cnt++;
		return;
	}

	for (int i = 0; i < n; i++) {
		check[row][i] = true;
		if (go(row, i)) {
			dfs(row + 1);
		}
		check[row][i] = false;
	}

}




int main() {


	scanf("%d", &n);

	dfs(0);

	printf("%d", cnt);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

조금 더 효율적으로 풀 수 있는 방법이 있을까요?

jemin9312 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말