*문제 출처는 백준에 있습니다.
문제 제목: N-Queen / 9663번 (골드 4단계)
문제 사이트: https://www.acmicpc.net/problem/9663
문제 설명

나의 풀이
def check(n, board, y, x):
# 위쪽 열 확인
for i in range(y):
if board[i][x] == 1:
return False
# 왼쪽 위 대각선 확인
i, j = y - 1, x - 1
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
# 오른쪽 위 대각선 확인
i, j = y - 1, x + 1
while i >= 0 and j < n:
if board[i][j] == 1:
return False
i -= 1
j += 1
return True
def solve(n, board, y, result):
if y == n:
result[0] += 1
return
for x in range(n):
if check(n, board, y, x):
board[y][x] = 1
solve(n, board, y + 1, result)
board[y][x] = 0 # 백트래킹
def main():
n = int(input())
board = [[0] * n for _ in range(n)]
result = [0] # 정답 저장용
solve(n, board, 0, result)
print(result[0])
if __name__ == "__main__":
main()
NxN 배열을 생성해서 0은 빈 상태 1은 퀸을 둔상태로 하나씩 두기 시작합니다! 퀸을 두었을 때 퀸이 다른 퀸으로부터 위협을 받는지 확인하고 두게 됩니다!

위 그림처럼 모든 경로를 파악하는 방법을 생각했습니다. 하지만 위 방법은 NxN 배열을 생성해서 파악하므로 시간 복잡도가 초과했습니다.
정답 코드
def solve(n, y, col, diag1, diag2, result):
if y == n:
result[0] += 1
return
for x in range(n):
if not col[x] and not diag1[y + x] and not diag2[y - x + n - 1]:
col[x] = diag1[y + x] = diag2[y - x + n - 1] = True
solve(n, y + 1, col, diag1, diag2, result)
col[x] = diag1[y + x] = diag2[y - x + n - 1] = False
def main():
n = int(input())
col = [False] * n
diag1 = [False] * (2 * n - 1)
diag2 = [False] * (2 * n - 1)
result = [0]
solve(n, 0, col, diag1, diag2, result)
print(result[0])
if __name__ == "__main__":
main()
위 코드는 board를 사용하지않고 col[x]: 열 충돌 체크, diag1[y + x]: 오른쪽 위 대각선 충돌 체크, diag2[y - x + n - 1]: 왼쪽 위 대각선 충돌 체크만 했습니다 그럼 매 순간 O(1)의 시간으로 해결할 수 있습니다.

※ 알아야 할 것
재귀함수를 이용하여 시뮬레이션을 진행하는 문제입니다!
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 랜선 자르기 / 1654번 / Python (0) | 2025.03.31 |
|---|---|
| 백준 / 2차원 배열의 합 / 2167번 / Python (0) | 2025.03.31 |
| 백준 / 문자열 게임 2 / 20437번 / Python (0) | 2025.03.27 |
| 백준 / 특정 거리의 도시 찾기 / 18352번 / Python (0) | 2025.03.26 |
| 백준 / 구간 합 구하기 5 / 11660번 / Python (0) | 2025.03.26 |