https://www.acmicpc.net/problem/9663
앞선 문제인 N과 M에서 사용되는 DFS를 활용한 문제이다.
중요한 아이디어는 같은 row에는 퀸이 하나밖에 존재할 수 없으며, 또 하나는 무조건 있다는 것이다.
이번 row에는 퀸이 어디에 와야할 지 column을 차례대로 늘려가면서 findColumn 함수를 통해 검사한다.
개인적으로는 row와 col이 서로 헷갈리고, for문의 range를 정하는 것 때문에 어려웠던 문제이다.
코드 설명은 주석으로 대신한다. 밑에서부터 보면 된다.
def isPossible(row, col): # 위 혹은 양방향 대각선에 퀸이 있는지 검사
# 좌우는 볼 필요가 없다. 하나의 row에는 하나의 퀸!
# 위 (아래를 안 보는 이유는 아직 다음 row 자체를 안 봤기 때문
for i in range(1, n): # 주의: 1부터다. 0으로하면 7번째 줄에서 자기 자신과 같은지 검사하게 됨
if row-i >= 0: # row를 1씩 줄여가되 음수가 되지 않도록 한다.
if chess[row-i][col]: # 퀸을 발견했다
return False
# \ 방향 대각선. row, col에서 1씩 빼면서 확인
for i in range(1, n):
if row-i >= 0 and col-i >= 0:
if chess[row-i][col-i]:
return False
# / 방향 대각선. row는 -1, col은 +1 (그림으로 생각해보자)
for i in range(1, n):
if row-i >= 0 and col+i < n:
if chess[row-i][col+i]:
return False
return True # 위 모든 검사를 통과했다면 그거슨 퀸
def findColumn(row):
global answer # 전역변수를 함수 내에서 수정하기 위해 global 선언
if row == n: # 하나의 row에는 하나의 퀸이 무조건 들어가므로, row가 n이라면 퀸의 자리를 다 찾은 것임
answer += 1
return
for col in range(n): # row는 정해져 있으니 column을 1씩 증가시키면서 확인한다
if isPossible(row, col): # 놓을 수 있다면
chess[row][col] = True # True로 퀸의 자리를 표시
findColumn(row+1) # 다음 row에서 퀸의 자리를 찾는다
chess[row][col] = False # 재귀가 끝난 후, 백트래킹해야하므로 다시 False로 돌려놓는다
n = int(input())
chess = [[False]*n for _ in range(n)] # 체스판. True면 퀸이 있는 자리
answer = 0
findColumn(0) # 인자는 row. 0번째 row부터 퀸이 들어갈 column을 찾는다.
print(answer)
'알고리즘 > 백트래킹' 카테고리의 다른 글
| 2차원 배열에서 조합 선택하기 (0) | 2019.12.20 |
|---|---|
| 14888. 연산자 끼워넣기 (0) | 2019.11.28 |
| 2580. 스도쿠 (0) | 2019.11.27 |
| 15650. N과 M (2) (0) | 2019.11.22 |
| 15649. N과 M(1) (0) | 2019.11.22 |