백준 BOJ 9663 N-Queen
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
접근 1
-
ㅋㅋㅋ 퀸 헷갈려서 검색해봄..ㅎ
-
모든 경우의 수 뽑아내야되니까
brute force문제 -
어쨌든 한 줄에 두 개 들어가는 게 불가능하니까
row와column중에 하나 정해서 기준 점 잡고 시작하기 -
다음 컬럼 하기 전에 가능한 인덱스 뽑고 시작하고 가능한 인덱스가 없으면 전으로 돌아가기(Backtracking) 라고 생각했으나 이상해져서 재귀로 풀었음 -
check 함수로 직선이랑 대각선에 퀸 있는 지 확인해준다.(대각선 거리 확인할 때는 절댓값 사용해주기)
Note
- 시간초과 되니까
Backtracking을 사용하기 - 파이썬 리스트에서 특정 값의 모든 위치 찾기 (다른 글에 따로 정리함)
- global 문을 사용하면 함수 안에서도 전역변수의 값을 수정 가능
global res
제출 1 - 시간초과
n = int(input())
res = 0
board=[0]*15
def recursive(x):
global res
if x == n:
res += 1
return
for i in range(n):
board[x] = i
if check(x):
recursive(x+1)
def check(x):
for i in range(x):
if board[x] == board[i] or abs(board[i]-board[x]) == x-i:
return False
return True
recursive(0)
print(res)
오답노트
시간초과 뜨고 욕이 한바가지로 나왔ㅋㅋㅋ 근데 또 python 3로는 안되고 pypy3으로는 풀릴 수 있게 만들 수 있다하질 않나...ㅋㅋㅋ
근데 조금 찾아보니까 애초에 파이썬에서는 같은 로직으로 풀어도 시간초과 나는 문제라서 파이썬 기준으로 이상하게 난이도 높아지는 문제라고 해서 다른 언어로 풀었다고 치고 넘어가기로 함 다른 사람들 보니까 그냥 풀고 시간 복잡도 줄이는 방법 계속 고민한 사람이 많아서 나도 찬찬히 고민해보기루
