[BOJ] 👸 N-Queens / 파이썬
글 작성자: 택시 운전사
반응형
👸 N-Queens
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
😃 나의 풀이
def nqueen(sol, n):
global count
if len(sol) == n: # 정답 배열(sol)의 길이가 n과 같아지면, count 증가
count += 1
return 0
candidate = list(range(n)) # 0부터 n-1까지를 후보 배열로 만든다.
for i in range(len(sol)):
if sol[i] in candidate: # 같은 열에 있는 지 확인
candidate.remove(sol[i]) # 같은 열에 있다면 후보에서 제외
distance = len(sol) - i
if sol[i] + distance in candidate: # 같은 대각성 상(+)에 있는 지 확인
candidate.remove(sol[i] + distance) # 같은 대각선 상에 있다면 후보에서 제외
if sol[i] - distance in candidate: # 같은 대각선 상(-)에 있는 지 확인
candidate.remove(sol[i] - distance) # 같은 대각선 상에 있다면 후보에서 제외
if candidate != []:
for i in candidate:
sol.append(i) # 후보의 요소를 정답 배열의 i+1로 추가
nqueen(sol, n) # 재귀적으로 다음 행도 확인
else:
return 0
count = 0
num = int(input())
for i in range(num): # 첫 행의 경우의 수
nqueen([i], num)
print(count)
N-Queens는 백트랙킹 알고리즘의 예시로 자주 이용되는 문제이다. 백트랙킹 알고리즘은 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모로 되돌아간 후 다른 자식 노드를 검색하는 알고리즘이다.
우선, 첫 행의 경우의 수를 산정하고 nqueen 함수에 넣는다. 그리고 각 행의 후보군을 만들어 위에 설명한 백트랙 알고리즘의 유망성이 있는 자식노드와 유망성이 없는 자식 노드를 구분하여 한 행씩 추가하면서, 완성된 정답 배열을 만들어 나간다.
참고자료
반응형
'Algorithm > Problem Solving' 카테고리의 다른 글
[프로그래머스] 💾 압축 - [3차] 2018 카카오 블라인드 채용 / 파이썬 (3) | 2019.02.02 |
---|---|
[프로그래머스] 📊 추석 트래픽 - [1차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT (0) | 2019.02.01 |
[프로그래머스] 🚍 셔틀버스 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT (0) | 2019.02.01 |
[프로그래머스] 이상한 문자 만들기 / 파이썬 (0) | 2019.01.31 |
[프로그래머스] 👨🎓 N으로 표현 / 파이썬 (0) | 2019.01.31 |
댓글
이 글 공유하기
다른 글
-
[프로그래머스] 💾 압축 - [3차] 2018 카카오 블라인드 채용 / 파이썬
[프로그래머스] 💾 압축 - [3차] 2018 카카오 블라인드 채용 / 파이썬
2019.02.02 -
[프로그래머스] 📊 추석 트래픽 - [1차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT
[프로그래머스] 📊 추석 트래픽 - [1차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT
2019.02.01 -
[프로그래머스] 🚍 셔틀버스 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
[프로그래머스] 🚍 셔틀버스 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
2019.02.01 -
[프로그래머스] 이상한 문자 만들기 / 파이썬
[프로그래머스] 이상한 문자 만들기 / 파이썬
2019.01.31