def Promising(pan, y, depth) :
for i in range(depth) :
if y == pan[i] or (depth-i == abs(y-pan[i])):
return False
return True
def Nqueen(n, pan, depth) :
global answer
if depth == n :
answer += 1
else :
for y in range(n) :
if Promising(pan, y, depth) :
pan[depth] = y
Nqueen(n, pan, depth+1)
def solution(n):
global answer
answer = 0
pan = [0] * n
Nqueen(n, pan, 0)
return answer
백트래킹 문제 첨 풀어보는거라 엄청 헷갈리고 .. 엄청 헤매고 ..
유튜브에서 N-Queen 강의도 봤는데 막상 강의 닫으니까 또 헤매고..웅웅,,,
나중가면 또 기억 못 할 것 같으니께 ,,
최대한 자세하게 설명 써놓겠다 ..!!
def solution(n):
global answer
answer = 0
pan = [0] * n
Nqueen(n, pan, 0)
return answer
n x n 표니까 2차원 배열로 만들어야 되지 않나? 라고 생각했는데
어차피 한 줄에 하나만 들어갈 수 있으니까 걍 1차원 배열에 열 번호를 넣으면 되겠다 !! 해서
예를 들어 4x4 판이면 pan = [0, 0, 0, 0] 형태로 초기화시켜줬다
그리고 Nqueen() 함수 파라미터에는 아래 3가지를 줌.
n : 가로/세로 길이
pan : 퀸의 열 번호가 담긴 1차원 배열
depth : 깊이 (0부터 시작)
def Nqueen(n, pan, depth) :
global answer
if depth == n :
answer += 1
else :
for y in range(n) :
if Promising(pan, y, depth) :
pan[depth] = y
Nqueen(n, pan, depth+1)
이게 이제 진전시키는 ..? 이라고 해야 되나
유망 조건에 맞으면 계속 재귀 함수로 부를 Nqueen 함수
depth 는 0부터 시작하니까 결국 끝까지 가서 n 과 같게 되면
조건을 모두 충족하는 거니까 answer += 1 해주고,
만약 그게 아니라면 열 하나씩 순회하면서
Promising() 함수 호출해서 유망한지 아닌지 확인함 !!
유망 함수에서 반환하는 값이 True 면
해당 열 번호 (y) 를 pan 배열에 집어넣고,
depth 하나 올려서 Nqueen() 재귀호출하면 됨.
def Promising(pan, y, depth) :
for i in range(depth) :
if y == pan[i] or (depth-i == abs(y-pan[i])):
return False
return True
이건 이제 해당 depth 에서 앞으로 진행할 열 번호 (y) 가
조건에 맞는지 확인하는 함수
1) 같은 열에 퀸 중복 x
2) 대각선에 퀸 중복 x
depth 이전 행까지 for 문 돌면서 위 2가지 조건을 검사함
하나라도 해당되면 바로 False 반환하도록 !! 그럼 끝 ㅎㅅ
'알고리즘' 카테고리의 다른 글
[프로그래머스 Lv2 - 2020 KAKAO BLIND RECRUITMENT] 문자열 압축 (Python) (0) | 2022.09.29 |
---|---|
[프로그래머스 Lv2 - 2021 KAKAO BLIND RECRUITMENT] 메뉴 리뉴얼 (Python) (0) | 2022.09.25 |
[프로그래머스 Lv2 - 2022 KAKAO BLIND RECRUITMENT] 양궁 대회 (Python) (3) | 2022.09.19 |
[프로그래머스 Lv2 - 2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기 (Python) (0) | 2022.09.16 |
[프로그래머스 Lv2 - 2022 KAKAO BLIND RECRUITMENT] 주차 요금 계산 (Python) (0) | 2022.09.16 |