[백준 9663][💛5] N-Queen (백트래킹)

🚀 난이도

💛 골드 5

🚀 문제

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

🚀 내 풀이

🔥 첫 번째 풀이 ❌ (시간초과)

프로그래머스의 N-Queen에서 제출했던 풀이와 비슷하지만 이번 백준의 N-Queen 에서는 통과하지 못했다..! 백준이 입력 크기가 더 크다. 프로그래머스는 N = 12, 백준은 N = 15 가 최대이다. 시간복잡도가 O(N!) 에 가깝기 때문에 3 만큼만 차이나지만 전체적인 시간복잡도 차이는 어마어마한 것이다..ㅠ ㅠ N = 15 에서는 통과하기 힘든 풀이였던 것 같다.

#include <bits/stdc++.h>

using namespace std;

int N, answer;
bool board[15][15];

void dfs(int row) {
	if (row == N) {
		++answer;
		return;
	}
	
	for (int col = 0; col < N; ++col) {
		bool cond1 = true;
		for (int i = 0; i < row; ++i) {
			if (board[i][col]) {
				cond1 = false;
				break;
			}
		}
		bool cond2 = true;
		for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
			if (board[i][j]) {
				cond2 = false;
				break;
			}
		}
		bool cond3 = true;
		for (int i = row - 1, j = col + 1; i >= 0 && j < N; --i, ++j) {
			if (board[i][j]) {
				cond3 = false;
				break;
			}
		}
		if (cond1 && cond2 && cond3) {
			board[row][col] = true;
			dfs(row + 1);
			board[row][col] = false;
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	
	dfs(0);
	
	cout << answer;
}

🔥 두 번째 풀이 ⭕

구글링 해보니 대부분 이 풀이로 제출하면 시간 초과 없이 통과하셨더 것 같다! 그런데 사실.. 첫 번째 풀이는 왜 시간초과가 나고 이 풀이는 왜 시간초과가 나지 않는지 잘 모르겠다..! 😥 두 풀이의 dfs 연산 횟수는 동일한데.. 첫 번째 풀이는 안에 있는 for문을 1 개 썼다는 정도이고 두 번째 풀이는 안쪽 for 문을 3 개 썼다는 정도의 차이인데 이 차이로 시간 초과가 발생한 것일까? 잘 모르겠다.. 알려주시면 너무 감사할 것 같아요 흑흑…

#include <bits/stdc++.h>

using namespace std;

int N, answer;
int queen[15]; // 인덱스는 row 가 된다. row 별 어느 col 에 두었는지 그 col 값을 기록.

void dfs(int row) {
	if (row == N) {
		++answer;
		return;
	}
	
	for (int col = 0; col < N; ++col) {
		queen[row] = col; 
		
		bool promising = true;
		for (int i = 0; i < row; ++i) {
			if (queen[i] == queen[row] || abs(queen[i] - queen[row]) == abs(i - row)) {
				promising = false;
				break;
			}
		}

		if (promising)
			dfs(row + 1);
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	
	dfs(0);
	
	cout << answer;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기