[C언어] 백준 9663 : N-Queen
흐름
n퀸 푸는 방법을 알았다.
https://www.youtube.com/watch?v=ltm-JX5R1pA&ab_channel=%EC%BD%94%EB%94%A9%EB%9E%A9CodingLab
여기서 한번 설명듣고 클론코딩해보고, 디버깅하면서 이해먼저했다.
그리고 안보고 다시 한번 해보고, 디버깅하면서 고쳤다. 이해 해버렸다.
주석으로 내가 헷갈렸던 부분과 논리를 적어보겠다.
#include <stdio.h>
int vx[16], vy[16];
int ft_abs(int a, int b)
{
if (a - b >= 0)
return a - b;
else
return (a - b) * - 1;
}
int n_queen(int x, int y, int n)
{
int i;
i = 0;
while (i < y) // 백트래킹을 위한 반복문
// 왜 i < y일까? 우리는 main에서 x좌표를 기준잡고 올렸다. 그리고 재귀로
// x좌표에 i, 즉 1씩 증가하고, y좌표는 고정되어있다.(+ 1만큼만)
// 그렇기에 y좌표까지만 고정하고, x좌표를 이동시키면서 진행시킨다.
// 이해가 안된다면 디버깅을 n = 4로잡고 다시 해보자.
{
if (y == vy[i]) // y좌표가 같을경우 가지치기
return 0;
if (x == vx[i]) // x좌표가 같을경우 가지치기
return 0;
if (ft_abs(x, vx[i]) == ft_abs(y, vy[i])) // 대각선이 같을경우 가지치기
return 0;
i++;
}
if (y == n - 1) // 좌표는 0부터 시작하기에 n - 1까지 세준다.
return 1;
vx[y] = x; // 왜 vx[y]일까? 위에서 말했듯 y는 고정시켜야 한다.
// vx[1] = 2, vy[1] = 1 이라고 하면, 두번째줄에 좌표가 2,1에 퀸을 놓는다는 의미.
vy[y] = y;
int count = 0;
i = 0;
while (i < n)
{
count = count + n_queen(i, y + 1, n);
i++;
}
return count;
}
int main()
{
int i, n;
int count = 0;
scanf("%d", &n);
i = 0;
while (i < n)
{
count = count + n_queen(i, 0, n);
i++;
}
printf("%d", count);
}
Author And Source
이 문제에 관하여([C언어] 백준 9663 : N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmainsain/C언어-백준-9663-N-Queen저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)