codingismylife   1년 전

제가 생각한 원리는, N개의 퀸을 적절히 배치하기 위해서는, 각 행에 하나의 퀸은 놔야 한다는 것에 착안하여, 

visited[x][y] = true;
V.push_back(make_pair(x, y));

for (int i = 0; i < N; i++)
{
for (int k = 0; k < V.size(); k++)
{
if (V[k].first - V[k].second != x + 1 - i && V[k].first + V[k].second != x + 1 + i && V[k].second!=i)
{
DFS(x + 1, i, depth + 1);
}
}

퀸을 놓은 좌표를 저장하고, 대각선 양방향(기울기 1, -1인 직선 위)와 같은 열에 놓지 않도록 하는 조건문을 작성하여 조건을 만족하면 DFS(x+1, i, depth+1)로 백트래킹을 진행하도록 하였습니다. 알고리즘 공부도 많이 하고, 나름 이해했다고 생각했는데 막혀서 시험 때문에 2달 동안 놓고 다시 생각해서 풀려고 해도 여전히 안되네요.... 제가 생각한 부분에 틀린점이 있는 것일까요 꼭 풀고 싶습니다 

thinker99   1년 전

if문에서 && 3번이 시간복잡도를 박살낼거같은 느낌이 드네요

최대 입력값인 n=15에서 마지막(15번째 퀸)을 놓으려면 저 && 3번을 15 * 14 * ... * 1 = 1,307,674,368,000번 해야하는데...

nqueen 문제는 row, column, 대각선1(y=x에 평행), 대각선2(y=-x에 평행)의 네 방향으로 체크를 해야하죠?

row는 백트랙의 depth에 녹여버릴 수 있고 (한 행에는 무조건 퀸 하나가 존재해야 하기에 굳이 따로 체크할 필요 없이 가장 첫 행 부터 퀸을 놓는다 생각)

column은 colchk[15], 대각선은 각각 diag1chk[29], diag2chk[29]를 두셔야 합니다

thinker99   1년 전

제 코드는 대각선 확인이 그렇게 효율적이지가 않아서 백트랙만 대충 보여드리자면 다음과 같습니다

codingismylife   1년 전

정말 감사합니다 너무 복잡하게 생각하고 있었네요 ㅠㅠ 열이랑 대각선 체크하는 배열을 따로 만들 생각을 못했는데 아이디어 얻어서 결국 풀어냈습니다 ㅠㅠ 정말 감사합니다 백트래킹 문제 3일 동안 이해하려고 여러 문제 풀어보고 있었는데 드디어 한 단계 올라간 느낌이네요 ㅠㅠ 

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