jun-wiki
치정극이 두려운 이유
에라이 재귀함수땜에 시간 존나 썼네
아무튼 지금은 N퀸에 대한 문제를 풀며
재귀함수와 for문의 다구리를 버틸거다
싸움은 쪽수라는 말이 있듯이
2대1은 꽤나 힘들다
재귀함수와 for문의 경우 손발이 꽤 잘맞아
더블 래리어트가 가능하다.
pos = [0] * 8 # 각 열에서 퀸의 위치를 출력
def put() -> None:
"""각 열에 배치한 퀸의 위치를 출력"""
for i in range(8):
print(f'{pos[i]:2}', end='')
print()
def set(i: int) -> None:
"""i 열에 퀸을 배치"""
for j in range(8):
pos[i] = j # 퀸을 j행에 배치
if i == 7 : # 모든 열에 배치를 종료
put()
else:
set(i + 1) # 다음 열에 퀸을 배치
set(0) # 0 열에 퀸을 배치
지금의 경우 무식하게 브랜치를 마구 뻗어나가는 형식으로,
가능한 모든 경우로 둔다고 보면된다.
이딴식으로 해서는 우리가 원하는 답을 못구하니
쓸데 없는 거 쳐내자
flag로 true, false로 제한을 두어 각 행에 퀸의 유무를 체크하자 ```py pos = [0] * 8 # 각 열에서 퀸의 위치 flag = [False] * 8 # 각 행에 퀸을 배치했는지 체크
def put() -> None: “"”각 열에 놓은 퀸의 위치를 출력””” for i in range(8): print(f’{pos[i]:2}’, end=’’) print()
def set(i: int) -> None: “"”i 열의 알맞은 위치에 퀸을 배치””” for j in range(8): if not flag[j]: # j 행에 퀸을 배치하지 않았으면 pos[i] = j # 퀸을 j 행에 배치 if i == 7: # 모든 열에 퀸을 배치를 완료 put() else: flag[j] = True # 퀸이 행에 잇음 set(i + 1) # 다음 열에 퀸을 배치 flag[j] = False # 퀸이 행에 업음
set(0) # 0열에 퀸을 배치
>훨씬 낫다 열뿐만 아니라 행까지 제한을 둠으로써<br>
가로세로는 해결했다. 퀸이 아닌 룩이었으면 이미 성공이다<br>
그치만 퀸이기에 조건을 더 추가해야한다.
<br>
>행과 마찬가지로 flag를 사용할 거다.<br>
대각선을 flag로 어찌하냐 할 텐데 대각선으로 새로운 라인을 생각하면 된다.<br>
>i행 j열의<br>
왼쪽 대각선 방향은 `i - j + 7`<br>
오른쪽 대각선 방향은 `i + j`<br>
로 써먹으면 된다.
<br>
```py
pos = [0] * 8 # 각 열에 배치한 퀸의 위치
flag_a = [False] * 8 # 각 행에 퀸을 배치했는지 체크
flag_b = [False] * 15 # 대각선 방향(↙↗)으로 퀸을 배치했는지 체크
flag_c = [False] * 15 # 대각선 방향( ↘↖)으로 퀸을 배치했는지 체크
def put() -> None:
"""각 열에 배치한 퀸의 위치를 출력"""
for i in range(8):
print(f'{pos[i]:2}', end='')
print()
def set(i: int) -> None:
"""i 열의 알맞은 위치에 퀸을 배치"""
for j in range(8):
if( not flag_a[j] # j행에 퀸이 배치 되지 않았다면
and not flag_b[i + j] # 대각선 방향(↙↗)으로 퀸이 배치 되지 않았다면
and not flag_c[i - j + 7]): # 대각선 방향( ↘↖)으로 퀸이 배치 되지 않았다면
pos[i] = j # 퀸을 j행에 배치
if i == 7: # 모든 열에 퀸을 배치하는 것을 완료
put()
else:
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
set(i + 1) # 다음 열에 퀸을 배치
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False
set(0) # 0열에 퀸을 배치
여왕들이 서로 안겹치게 두기가 이리 빡세다.
괜히 퀸 하나만 주는게 아니다.
권력있다고 막 첩실 들이고 처 늘리다간 좋은 꼴 못본다.
그러니 앞으로 체스 둘 때에 폰을 퀸으로 승급시키는 건 사려 깊게 고민해보자.
치정극으로 인한 체크메이트는 두려우니 말이다.