(문제 해결을 위한 저의 아이디어가 포함되어 있으니, 정말 모르겠다 하시는 분들만 코드를 봐주세요. 양해 바랍니다.)
보통 N-queen을 푸신분들이 이 문제를 도전합니다. 하지만 저는 이 문제를 바로 푸는 것을 권장드리지 않습니다. 그 이유로는 N-Queen 문제랑은 조금 다른 사고력을 필요로 하거든요. 이 글에서는 그를 이야기 하고자 합니다.
N-Queen은 퀸을 서로 공격하지 못하게 놓는 문제입니다. 퀸은 룩(상하좌우)과 비숍(대각선)이 합쳐진 기물이죠. 그래서 조금의 트릭으로 (룩과 관련된 트릭) 시간복잡도를 개선할 수 있습니다. 그러나 이 문제는 비숍을 서로 공격하지 못하게 놓는 문제입니다. 비숍은 대각선으로만 공격하기 때문에, N-Queen에서 수정해서 제출했다가는 시간초과가 납니다. 이를 어떻게 개선할까요?
우리는 비숍의 행마와 체스판의 타일 색깔을 이용할 겁니다.
비숍은 자신이 밟은 칸의 색깔로만 이동할 수 있죠? 그렇다면 다른 색깔을 확인할 필요가 없게됩니다. 이 방법을 검정 타일과 흰 타일 두 번 백트래킹을 돌려준 다음, 그 두 결과를 합치면 정답이 나옵니다. 어떤 칸을 하얀색, 검정색으로 정할지는 직접 해보시기 바랍니다.
factories 1년 전 2
(문제 해결을 위한 저의 아이디어가 포함되어 있으니, 정말 모르겠다 하시는 분들만 코드를 봐주세요. 양해 바랍니다.)
보통 N-queen을 푸신분들이 이 문제를 도전합니다. 하지만 저는 이 문제를 바로 푸는 것을 권장드리지 않습니다.
그 이유로는 N-Queen 문제랑은 조금 다른 사고력을 필요로 하거든요. 이 글에서는 그를 이야기 하고자 합니다.
N-Queen은 퀸을 서로 공격하지 못하게 놓는 문제입니다. 퀸은 룩(상하좌우)과 비숍(대각선)이 합쳐진 기물이죠. 그래서 조금의 트릭으로 (룩과 관련된 트릭) 시간복잡도를 개선할 수 있습니다.
그러나 이 문제는 비숍을 서로 공격하지 못하게 놓는 문제입니다. 비숍은 대각선으로만 공격하기 때문에, N-Queen에서 수정해서 제출했다가는 시간초과가 납니다.
이를 어떻게 개선할까요?
우리는 비숍의 행마와 체스판의 타일 색깔을 이용할 겁니다.
비숍은 자신이 밟은 칸의 색깔로만 이동할 수 있죠? 그렇다면 다른 색깔을 확인할 필요가 없게됩니다. 이 방법을 검정 타일과 흰 타일 두 번 백트래킹을 돌려준 다음, 그 두 결과를 합치면 정답이 나옵니다. 어떤 칸을 하얀색, 검정색으로 정할지는 직접 해보시기 바랍니다.