backstone   1년 전

N-Qeen문제를 풀기위해 다음과 같은 생각으로 접근했습니다.

- 큐를 이용한 백트레킹

- 한 행에 하나의 퀸이 있어야 한다는 생각으로, 각 행에 무슨 열에 퀸이 있는지 기록함

(int[] 배열 -> 

인덱스 : 퀸의 행의 값, 

int[0] : 기록된 길이, 

int[1] ~ int[n] : 퀸의 열값, 

int[n+1] : 다음 갈 수 있는 열의 값의 기록(어디서 부터 접근할 수 있는지 표시 ->  중복  방문 방지))

재귀 호출을 이용한 방법은 스택 오버플로우 발생시킬 것 같아 안썼습니다만, 해당 문제는 재귀 호출을 사용해서만 풀 수 있는지 궁금합니다.

만일 제 방식대로 큐를 이용한 백트레킹 기법으로도 해결한 수 있다면 조언 부탁드립니다.

시간 내서 제 글을 읽어 주셔서 감사합니다.😁

adfsfsf   1년 전

현재 코드를 보면 한 번의 재귀마다 '전체 보드의 상태'를 새로 생성하고 있습니다.
즉, 실질적으로는 N*N 배열을 계속 관리하는 셈입니다.

다른 게시글들을 이미 읽어보셨는지는 모르겠지만, 실제로는 하나의 N 크기 배열만으로도 문제를 풀 수 있습니다.

각 칸마다 현재 열에 넣어줄 행을 적어주고, 다음 빈 열로 이동하여 가능한 행들을 순차적으로 검토하는 방식을 쓰면 됩니다.

factories   1년 전

모든 재귀 문제들은 반복문으로 치환해 풀 수 있습니다. 단지 반복문의 개수가 많아지니 재귀함수를 다루게 된 것이지요...

윗 분 말씀대로 배열 3개만으로 퀸의 공격여부를 확인 할 수 있습니다. 인덱스를 잘 활용해 보세요.

backstone   1년 전

말씀대로 하나의 배열과, 방문했는지 확인하는 용도의 2차 배열로 접근하니, 메모리 초과 발생하지 않고 잘 해결했습니다!

정말 감사합니다.

덕분에 문제 해결할 수 있었습니다!😄

adfsfsf   1년 전

해결하셨다니 다행이네요.

별도로, 제가 하나면 충분하다고 한 이유를 적어보겠습니다.

배열이 [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개여도 해결되었나 보네요.

댓글을 작성하려면 로그인해야 합니다.