어떤 블로그에서 봤는데, 이분탐색은 숫자 맞추는 up down 게임이라고 하더라... 좋은 예시인 것 같다..
2110 공유기 설치
ㅇ
9663 N-Queen
python으로는 실패하고... 동일 코드로 pypy로는 통과하는 문제인데 간혹 이런 문제가 나오는데 로직이 문제인지 잘 모르겠다... pypy로만 통과되는 문제면 그만큼 시간관리가 엄격하다는 건데, 그래서 그런지 검색해서 나오는 코드마다 모두 일차원 배열로 풀었다. 이차원 배열은 시간이 더 많이 걸려서 그런가보다 ...
일차원 배열 board를 선언했는데 이것의 의미는 board[ i ] = j 일 때 [ i, j ]에 퀸을 놓겠다는 의미이다. 이것을 잘 기억해두어야 한다. 우리가 문제를 풀 때 사용하는 함수는 2가지이다. 퀸을 놓을 수 있는지 체크해주는 함수가 chk_queen 이라고 하였고, 그것은 mainF 함수에서 사용된다.
<mainF>
시작은 mainF 함수에 0을 넘겨줌으로써 시작되는데 이것은 0행부터 시작한다는 의미이다. mainF의 탈출 조건은 x == n 이라고 해놓았는데, 행 x가 n*n 보드판을 모두 돌았을 때를 의미한다고 생각했다. 아직 행이 남았을 경우 else로 넘어가서 chk_queen을 다룰건데, 이때 for문으로 n까지 모두 체크해주어야 한다. board[x] = i 라고 해놓은 것은 0행부터 시작해서 [0, i] , [0, i+1 ] .. 처럼 각 열들을 다루겠다는 의미이다. 만약 chk_queen(x) 가 true라면 놓을 수 있다는 의미이므로 다음행으로 넘어간다. 이를 mainF(x+1)로 표현하고 놓을 수 있다면 바로 다음 행으로 넘어가는 이유는 퀸이 각 행마다 하나씩밖에 못놓이기 때문이다.
<chk_queen>
chk_queen에서는 퀸을 놓을 수 있는지 없는지 체크해준다. 퀸을 놓지 못하는 경우는 두가지이다.
- 같은 열(j값)에 놓인 경우, 즉 row[i] = j 일때 j값이 서로 같은지 확인한다. 같은 행은 확인할 필요가 없다. 왜냐하면 i값 자체가 행을 나타내기 때문에 유일하고, 애당초 mainF에서 놓을 수 있다면 바로 mainF(x+1)로 다음 행으로 넘겨버렸기 때문이다. 그래서 같은 행을 다루지 않는 것은 저 코드로 대체할 수 있다.
- 대각선 체크가 중요한데, 퀸을 맨 위에 0행부터 아래로 채워나가는 형식이므로 대각선 4개(왼쪽위, 왼쪽아래, 오른쪽위, 오른쪽아래)중에서 왼쪽위, 오른쪽위 값만 체크하면 된다. 아래는 다음 행이므로 애당초 채워져있지 않다. 그래서 아래쪽은 살피지 않아도 되고 왼쪽위와 오른쪽 위만 체크해준다. 이것은 코드를 보고 이해했는데, 다음 코드를 보자.
for i in range(x): # 현재까지 진행한 행(x값)까지만 체크하는 for문
if board[x] == board[i] or abs(board[x] - board[i]) == abs(x - i):
return False
return True
if문의 or을 기준으로 왼쪽이 j값이 같은지 확인하는 부분, 즉 같은 열인지 체크하는 코드이다.
if문의 or을 기준으로 오른쪽이 대각선을 체크하는 코드이다. 이것이 왜 대각선 코드냐하면, abs(x-i)라는 것은 행끼리 떨어진 거리를 나타낸다. 어떤 칸에서 왼쪽도 위쪽으로 한칸, 오른쪽도 위쪽으로 한칸 동일하게 떨어져 있다면 바로 윗 행임을 알 수 있다. 이것이 두칸이라면 두칸 위인 행임을 의미한다. 그리고 board의 값은 열이라고 말했으므로 abs(board[x] - board[i])는 열끼리 떨어진 거리를 의미한다. 따라서, 열끼리 떨어진 거리와 행끼리 떨어진 거리가 같다면 이것은 곧 대각선을 의미한다.
위 그림을 보자. 동그라미를 기준으로 왼쪽X와 오른쪽X는 모두 가로로 한칸, 세로로 한칸씩 떨어져있다. 별표 또한 같은 맥락으로 가로로 두칸, 세로로 두칸 떨어져 있다. 즉 가로로 떨어진 거리와 세로로 떨어진 거리가 같다면 그것이 곧 대각선을 체크하는 것을 말한다. 따라서 위에서 떨어진 거리를 체크하는 것으로 코드를 작성한 것이다.
n = int(input())
cnt = 0
board = [0] * n
# 퀸을 해당 위치에 놓을 수 있는지 없는지 검증하는 함수
def chk_queen(x):
for i in range(x): # 현재까지 진행한 행(x값)까지만 체크하는 for문
if board[x] == board[i] or abs(board[x] - board[i]) == abs(x - i):
return False
return True
def mainF(x):
global cnt
if x == n:
cnt += 1
return
else:
for i in range(n):
board[x] = i # 파라미터로 넘어온 x는 0이므로 0행부터 놓기 시작, [x,i]에 퀸을 놓는다는 의미 즉 n번째까지 쭉 찍어봄
if chk_queen(x): # 놓을 수 있다면
mainF(x + 1) # 그 다음 행을 다룸, 왜냐하면 각 행마다 1개씩이므로 놓을 수 있으면 바로 행 넘어감
mainF(0)
print(cnt)
