코드 복사/붙여넣기 하는 당신이 아름답습니다.

9663 : N-Queen

풀이

룰루랄라 백트래킹을 해주자~

x 모양 대각선을 + 모양으로 뒤집어서 생각할 때

(x, y) -> (x+y, x-y)를 이용하면 편하다.

말이 조금 이상하지만 아무튼 저렇게 넣고 출력해보면 대강 이해 갈 것이다.

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

위 문제도 이 테크닉을 써서 풀 수 있겠다.

코드

#include <stdio.h>

int n, ans, u[33], l[33], r[33];
void dfs(int h, int c) {
	if (c == n) {
		ans++;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (u[i] || l[i + h] || r[i - h + 14]) continue;
		u[i] = l[i + h] = r[i - h + 14] = 1;
		dfs(h + 1, c + 1);
		u[i] = l[i + h] = r[i - h + 14] = 0;
	}
}

int main() {
	scanf("%d", &n);
	dfs(0, 0);
	printf("%d", ans);
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-11-01 11:09

Read more posts by this author