퀸을 놓을 때마다 막히는 칸들을 일일이 표시하는 대신, 막히는 열, 대각선, 반대각선 번호만 표시해 두면 충분합니다.
제 코드를 참고용으로 첨부합니다. https://www.acmicpc.net/source...
9663번 - N-Queen
퀸을 놓을 때마다 막히는 칸들을 일일이 표시하는 대신, 막히는 열, 대각선, 반대각선 번호만 표시해 두면 충분합니다.
제 코드를 참고용으로 첨부합니다. https://www.acmicpc.net/source...
댓글을 작성하려면 로그인해야 합니다.
tnsbro 9달 전
문제를 풀기 위해 많은 고민을 해봤고 n값이 커질수록 처음에 놓았던 퀸이 나중에 미치는 영향을 계산하기는 어렵다 판단하여, 리스트에서 퀸이 놓이면 안 되는 자리를 다 기록하는 식으로 알고리즘을 만들었습니다. 그러다보니 너무 시간이 오래 걸려 pypy3로 겨우 통과했네요..ㅎ 이 문제의 요점이 아마도 정말 많은 경우의 수를 최대한 안 되는 경우를 미리 판단하여 가지치기 하는 것이라고 생각이 드는데, 방법이 떠오르지 않습니다 ㅠㅠ
제 코드는 퀸의 영향이 없는 자리를 찾았을 때, 그 위치에 퀸을 두고 그 퀸이 영향을 미치는 칸을 1로 채우는 것입니다. 그 후 재귀를 사용해 계속해서 경우를 나누었고, n*n의 칸에 n개의 퀸이 들어가야 하니,한 줄에 하나씩 퀸이 위치할 수 밖에 없어 퀸의 영향이 없는 자리는 한 줄만 확인하고 넘겼습니다.
제가 놓치고 있는 백트래킹의 기본적인 원리나 이 문제에서 유용하게 사용될 수 있는 백트래킹 관련 이론?들 알려주시면 감사하겠습니다!