[문제풀이] N-Queen

문제

문제 요약:

대충 체스판이 4x4면 퀸을 중복되지 않게 4기를 두는 문제이다.

풀이 시간: 8시간
접근 방법:
1.패턴 분석 (4시간)-알고리즘이라길래 패턴이 있는줄;;
2.N = 6 까지 그리며 옮겨보기
3.2번 진행 시 n = 5 ~ 6으로 갈때 줄어드는 것을 보고 단순 반복 구현으로 판단.
결과: X

난관
1. 퀸s 위치 구현
2. 역 대각선 검증
3. 2차원 배열 구현이 어려워 교재 참고.

n = int(input())
pos = [0] * n
flag_a = [False] * n            #flag_a 같은 col안에 퀸이 있는지 비교용 배열
flag_b = [False] * ((n * 2)-1)  #flag_b 대각선 우상단 비교용 배열
flag_c = [False] * ((n * 2)-1)  #flag_c 대각선 우하단 비교용 배열
count = 0

def put() -> None: #출력문
    
    for i in range(n): #pos[0~n] 한줄 출력
        for j in range(n):
            # print(f'{pos[i]:2}', end='')
            print('◆' if pos[i]==j else '◇', end='' )
        print()
    print()
    
    
    
def set(i:int)-> None:
    
    for j in range(n):
        if (    not flag_a[j]                 # j반복에서 flag[j] 값이 False 가 아니면 == True
            and not flag_b[i+j]             # 
            and not flag_c[i-j + (n-1)]
            ):
            
            pos[i] = j  # 퀸을 체스 i 번째에 둠
            if i == n-1: #n

                put()
            else:
                flag_a[j] = flag_b[i + j] = flag_c[i - j + (n-1)] = True 
                set(i+1)
                flag_a[j] = flag_b[i + j] = flag_c[i - j + (n-1)] = False
                

set(0)
    

핵심

찾아보니 DFS방식으로 모든 경우에 수를 순회하며,
조건에 맞는 경우 출력 Or 카운팅 방식으로 접근 해야 했다.
조건
1. 2차원 배열활용이 아닌 여러 1차원 bool 배열을 활용하여 조건 비교
2. 대각선 비교용 bool 리스트 개수가 n*2-1
3.

코드 설명,

변수

n = 전달 받을 인자값
pos(position) =  0이 삽입된 원소를 n개만큼 [list] 생성 - 체스판이라 가정
flag_a = Bool열 리스트로, pos와 똑같은 개수인 n만큼 생성.
flag_b = 대각선 우상단 비교용 Bool 리스트 (개수가 (n*2)-1 인 이유가 핵심
flag_c = 대각선 우하단 비교용 Bool 리스트
i = 재귀적(함수)으로 반복되며 체스판에 n번째 퀸을 둘 자리 변수
j = 반복적(반복문)으로 함수내에서 조건검색할 때, 필요 대표적으로 flag_a 변수의 x(col-가로)위치 비교

함수

set = 재귀함수로, j값으로 다음 퀸 놓을 위치를 찾고 계산할 메인 함수.
for j in range(n)
다음 퀸을 반복적으로 놓기 위해, 반복 필요
이후, 첫 if문에서 퀸이 체스판에 놓이는 작업이 수행됨. pos[i] = j
다음 if에서 i를 확인하여 퀀을 n만큼 놓았는지 확인하며, 아닐 시 다음 퀸을 놓기 위해.
flag_a,b,c  bool 리스트 업데이트
i를 +1하여 재귀 호출

과정 요약

1. 함수가 한번 거치고 재귀 호출 시 i+1이 되어 pos[1]번째 자리에 퀸을 두게 된다.
   이때 flag_a,b,c의 Bool 리스트를 비교하여 놓을 수 있는 위치 인 경우 pos[i]=j가 실행되며 그렇지 않을 경우 j++ 이 되며 반복 될 것이다.

2. 아래는 for 문을 거쳐 마지막 퀸만 배치되면 되는 과정이다 하지만 pos[0] = 0일 때, 모든 퀸이 체스판위에 놓일 경우에 수는 없기에 put() 함수 호출은 되지 않으며 재귀호출 된 함수들이 call stack에서 빠져나가며 상단 재귀함수로 돌아간다.
   

3.반복 이후에 다음 pos[0] = 1로 배치 되며 그림과 같이 첫 퀸의 자리가 이동 할 것이다.

4.pos[0] = 1일 때, 모든 퀸이 조건에 닿지 않고 체스판에 놓일 수 있다.

이것이 반복되며 퀸이 모두 배치 될 경우에만 출력 또는 카운팅 된다.

조건

1.대각선 논법

코드와 이미지를 보자

	if문안에 
	 not flag_b[i + j] == True

flag_b[i+j]가 False라면 참이라는 뜻이다.
이게 뭔 소리인가 이해가 절대 안 될텐데 걱정해라.
이해 안되는게 맞다.

그래도 미래의 나를 위해 설명 ㄱㄱ.
flag_b,c는 bool리스트로 대각선을 비교 하는 수식인데 이게 뭔 의미고 왜 가능할까?

코드를 조금 더 내려와서 보면

else:
flag_b[i + j] = True

부분이 있다.
그림에 회색박스와 같이 0,2 좌표에 있는 퀸이 있다고 가정하면,
위 코드와 같이 flag[2]에 값을 True가 체크가 되고 다음 재귀때 i는 i+1이 된 상태일 것이다.
그 안에서 for문이 돌다가 pos[1] = 1일 때,
if문에 있는 조건 flag_b[i+j]가 False인지 확인 할 것이다.
저번 재귀에서 flag_b[2]를 True로 바꿔 놨기 때문에 이번 조건에서는 True이기에 해당위치에 놓을 수 없다는게 판명 된다.

놀랍게도 대각선에 위치한 i+j는 모두 동일한 값을 가진다.

여기까진 이해할만하다 이젠 역대각선을 구현할 차례인데 이건 말로만 들으면 이해는 될 거같은데 내 머리가 이해를 거부하는 느낌이 들기 시작한다.
무섭지만.. 한번 알아보자.

	if문안에
	 not flag_b[i - j + (n-1)]

역대각선은 많이 어렵다
뭔가 비슷하면서도 이해하려고 하면 더 햇갈리기 때문이다.

그럼에도 불구하고 설명하자면,
현재 퀸을 pos[0] = 3 으로 두었다고 가정하자
이후 코드로는 flag_c[i-j]+(n-1) = True 라는 코드를 볼 수 있다. (=2)
다음 줄로 넘어가서, 다음 퀸이 pos[1]=4에 위치한 경우, flag_c[i-j]+(n-1) 의 값은 똑같이 2일 것이다.

똑같이 대각선 수식이지만 n-1이 붙은걸 확인 할 수 있다.
왜 n-1을 붙일까?!?

아래 이미지를 보고 조금이라도 이해해보자.

표가 거꾸로 되긴 했는데 설명하는데 문제는 없을 것 같다.
대각선에서 i+j로 비교가 가능하듯이 역대각선은 i-j로 비교가 가능하다.
(같은 색갈끼리 같은 flag_C 인덱스임
예) 그림에서 Flag[0] == 주황색 범위
But!
파이썬 문법에서 음수로 접근 할 수는 있지만, 정확히 내가 원하는 수에 접근을 하지 못할 것이다.
그렇기에 n의 크기 만큼 전체를 밀어내서 스케일 업 해버리는 거다.
나도 설명하면서 더 쉽게 설명을 못하는게 개탄스러울 뿐이다.

짜잔
이해가 안되면 이미지 두개를 비교해보자
얼핏 이해가 될 것 같기도 하다.
코드에서는 Flag를 Bool 타입으로 대각선 유무를 판별하기에 bool 리스트에 인덱스를 정수로 해줄 필요가 있다.

이어서,
대각선 판별 변수가 왜 2*n-1 인가?
도 설명하겠다.
위에 첨부한 이미지와 같이 수직,수평을 판별할 경우에 i,j와 같은 n값을 단순하게 쓰면 되지만
대각선을 경우 2*n-1을 써야지만 정확한 판별이 가능 할 것이다.

PS. 이걸 읽는 모든이들은 복 받은거다. 난그림도 없이 이걸 이해하려고 8시간 이상을 썼다.