현재 코드를 보면 한 번의 재귀마다 '전체 보드의 상태'를 새로 생성하고 있습니다.
즉, 실질적으로는 N*N 배열을 계속 관리하는 셈입니다.
다른 게시글들을 이미 읽어보셨는지는 모르겠지만, 실제로는 하나의 N 크기 배열만으로도 문제를 풀 수 있습니다.
각 칸마다 현재 열에 넣어줄 행을 적어주고, 다음 빈 열로 이동하여 가능한 행들을 순차적으로 검토하는 방식을 쓰면 됩니다.
9663번 - N-Queen
해결하셨다니 다행이네요.
별도로, 제가 하나면 충분하다고 한 이유를 적어보겠습니다.
배열이 [1,3,5,6,6]과 같이 있다고 해볼게요.
그럼 이번에 확인할 열은 4번 열, 빈 행은 2, 4임을 알 수 있습니다.
이 상황에서 4번 열에 2번을 먼저 넣으면 5번 열의 값을 자동으로 채우고, 재귀 기준으로, 5번이 빈 상태로 돌아옵니다.
이제 4번 열에서는 다음 값이 4임을 아니 4를 넣어봅니다.
4번 열도 다 확인했으면 3번 열로 돌아가고, 5는 마지막 행이니 2번 열까지 돌아갑니다.
이제 2번 열은 3의 다음 행인 4를 넣어봅니다.
이런 식으로, 항상 '가능한 행 중 가장 작은 값부터 검토'한다면 방문 배열도 굳이 쓸 필요가 없습니다.
그렇기에 하나의 배열이라고 했었습니다만 다행히 문제의 N이 최대 15여서 3개여도 해결되었나 보네요.
댓글을 작성하려면 로그인해야 합니다.
backstone 1년 전
N-Qeen문제를 풀기위해 다음과 같은 생각으로 접근했습니다.
- 큐를 이용한 백트레킹
- 한 행에 하나의 퀸이 있어야 한다는 생각으로, 각 행에 무슨 열에 퀸이 있는지 기록함
(int[] 배열 ->
인덱스 : 퀸의 행의 값,
int[0] : 기록된 길이,
int[1] ~ int[n] : 퀸의 열값,
int[n+1] : 다음 갈 수 있는 열의 값의 기록(어디서 부터 접근할 수 있는지 표시 -> 중복 방문 방지))
재귀 호출을 이용한 방법은 스택 오버플로우 발생시킬 것 같아 안썼습니다만, 해당 문제는 재귀 호출을 사용해서만 풀 수 있는지 궁금합니다.
만일 제 방식대로 큐를 이용한 백트레킹 기법으로도 해결한 수 있다면 조언 부탁드립니다.
시간 내서 제 글을 읽어 주셔서 감사합니다.😁