4 × 4 체스판에 서로 공격할 수 없도록 퀸 4개를 놓는 N-Quee… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
4 × 4 체스판에 서로 공격할 수 없도록 퀸 4개를 놓는 N-Queens 문제를 백트래킹(backtracking)으로 해결하고자 한다. 다음 <보기>의 조건에 따라 탐색을 진행할 때, 가장 먼저 찾게 되는 해로 가장 옳은 것은?
<보기>
(조건1) 좌표 체계는 체스판의 가장 왼쪽 위 칸을 (1행, 1열)로 정의한다. 행 번호는 위쪽에서 아래쪽으로 1부터 4까지, 열 번호는 왼쪽에서 오른쪽으로 1부터 4까지 순서대로 부여된다.
(조건2) 탐색 순서는 1행부터 4행까지 행 번호가 증가하는 순서대로 퀸을 배치한다.
(조건3) 후보 시도는 각 행 내에서는 1열부터 4열까지 열 번호가 작은 칸부터 순서대로 퀸 배치를 시도한다.
(조건4) 퀸은 가로, 세로, 대각선 8방향에 대하여 자기 자신이 위치한 칸을 제외한 모든 칸을 공격할 수 있다. 예를 들어, (1행, 1열)에 위치한 퀸은 (1행, 1열)을 제외하고 1행 전체, 1열 전체, (2행, 2열), (3행, 3열), (4행, 4열)을 공격할 수 있다.
(조건5) 백트래킹 규칙은 어떤 칸에 퀸을 놓았을 때 이미 배치된 다른 퀸에게 공격받는 위치라면 같은 행의 다음 열을 시도한다. 만약 특정 행에서 4개의 열을 모두 시도했음에도 퀸을 놓을 수 없다면, 직전 행으로 되돌아가(backtrack) 해당 행에 배치된 퀸의 위치를 다음 열부터 다시 탐색한다.
(조건6) 해는 1행, 2행, 3행, 4행에 놓인 퀸의 열 번호를 순서대로 나열하여 표기한다.
1
(1, 2, 3, 4)
2
(2, 4, 1, 3)
3
(2, 4, 3, 1)
4
(3, 1, 4, 2)
해설

가장 먼저 찾는 해는 (2, 4, 1, 3)이다.

1행을 1열에 두면 2행 3열 뒤 3행에 놓을 곳이 없고, 2행을 4열로 옮겨도 3행 2열 뒤 4행에 놓을 곳이 없어 1행 1열로는 해가 없다.

1행을 2열로 옮기면 2행 4열, 3행 1열, 4행 3열이 차례로 놓여 해가 완성된다.

  • (1, 2, 3, 4): 모든 퀸이 한 대각선 위에 있어 서로 공격한다.
  • (2, 4, 3, 1): 2행 4열과 3행 3열이 대각선으로 맞닿는다.
  • (3, 1, 4, 2): 올바른 해이지만 1행 3열은 1행 2열보다 나중에 시도되므로 그다음에 찾게 된다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기