문제 출처 : https://www.acmicpc.net/problem/9663
문제 파악
체스는 잘 모르지만 이 문제를 풀기 위해서는 퀸의 이동 방식에 대해 알아야 한다.
퀸의 이동방식
퀸은 가로, 세로, 대각선 어느 방향으로든 몇 칸이든 이동 가능하다.
즉,
같은 행(row) 에 있으면 공격 가능
같은 열(col) 에 있으면 공격 가능
같은 대각선(↘, ↙) 상에 있으면 공격 가능
문제에서는 NxN 판 위에서 N개의 퀸이 서로 공격할 수 없게 놓는 방법의 수를 구하라 하였다.
퀸끼리 위 세 방향 중 하나라도 겹치면 놓을 수 없다.
이 문제에서는 NxN 테이블에 N개의 퀸을 놓아야 하니
우선 1개의 행(가로)에 1개씩의 퀸을 놓는 것은 고정이다.
그리고 체크해야 할 것은
1. 같은 열에 속한 퀸이 존재하는 지
2. 같은 대각선에 속한 퀸이 존재하는 지
이렇게 두가지이다.
그리고 이 문제는 특이한 것이
한 행(가로) 당 한 개의 퀸이 존재하는 것이 사실이니
2차원 배열로 체스판을 그리는 것이 아닌
1차원 배열로 퀸의 위치를 선언할 수 있다.
2차원 보드를 직접 쓰지 않고, 길이 N의 1차원 배열 queen으로 표현한다.
queen[r] = c → r행에 있는 퀸이 c열에 놓였다는 뜻
예: N=4일 때 queen = [1, 3, 0, 2]
0행→1열, 1행→3열, 2행→0열, 3행→2열
각 행에 정확히 하나씩만 배치되므로 행 충돌은 자연스럽게 배제된다.
. Q . .
. . . Q
Q . . .
. . Q .퀸의 위치를 표시할 수 있다.
check()
우선 같은 열인지, 그리고 같은 대각선인지 체크함수
check()는 이렇게 구현할 수 있다.
# r번째 행에 둔 퀸이 이전 행의 퀸들과 충돌하는 지 확인
def check(r):
for i in range(r): # 이전 행들 0~r-1
# 같은 열 or 같은 대각선에 있으면 False
if queen[r] == queen[i] or abs(queen[r] - queen[i]) == (r-i): # 같은열
return False
# 그렇지 않고 다 통과하면 True
return Truecheck함수의 인자로는 r을 받는데
r은 row로 행이다.
check(2)를 하면 2번째 행에 퀸을 둘건데 이때 2 이전의 행들과 둘 퀸이 충돌하는 지를 확인한다는 의미이다.
확인은
1. 같은 열
2. 같은 대각선
체크가 필요한데
같은 열의 경우 이전 행을 돌면서
queen[r](현재 행) == queen[i](이전 행)
일치 하는 지를 봄으로써 같은 열 체크가 가능하다.
같은 대각선의 경우
행 차이와 열 차이가 같으면 대각선에 있다고 알 수 있다.
그래서
abs(queen[r] - queen[i]) == (r-i): 조건문을 통해 따질 수 있다.
백트래킹
r행에 대해 가능한 모든 열 c를 시도한다. 유효하면 다음 행으로 진행하고, r==N이 되면 유효한 배치를 하나 찾은 것이다.
def dfs(r):
global count
if r == N: # 모든 행에 배치 완료
count += 1
return
for c in range(N): # 0 ~ N-1 열 시도
queen[r] = c
if check(r): # 이전 행들과 충돌 없으면 다음 행으로
dfs(r + 1)해답 및 풀이
import sys
input = sys.stdin.readline
N = int(input())
queen = [0] * N # 퀸의 위치
count = 0
# r번째 행에 둔 퀸이 이전 행의 퀸들과 충돌하는 지 확인
def check(r):
for i in range(r): # 이전 행들 0~r-1
# 같은 열 or 같은 대각선에 있으면 False
if queen[r] == queen[i] or abs(queen[r] - queen[i]) == (r-i): # 같은열
return False
# 그렇지 않고 다 통과하면 True
return True
def dfs(r):
global count
# 종료 조건
if r == N: # 모든 행에 퀸을 배칭했다면
count += 1
return
for c in range(N):
queen[r] = c # r행 c열에 퀸 배치 시도
if check(r): # 이전 행들과 충돌하지 않으면 다음 행으로
dfs(r + 1)
dfs(0)머리로 이해하긴 쉽지 않지만
흐름은 이러하다.
dfs(0) → 0행에서 열 0~3을 시도
dfs(1) → 1행에서 열 0~3을 시도
dfs(2) → 2행에서 열 0~3을 시도
dfs(3) → 3행에서 열 0~3을 시도
dfs(4) → r == N → 모든 행에 퀸을 성공적으로 배치 → count++
