[내일배움캠프 4-4일] N-Queen, 백트래킹

N-Queen

N*N 체스판이 있을 때 N개의 퀸끼리 서로 잡아먹지 못하게 배치하는 경우의 수를 구한다.

모든 경우의 수를 탐색한다면 N이 늘어남에 따라 연산이 엄청나게 늘게 됨.

여기서 백트래킹이 필요한 것.

---

백트래킹

필요없는 부분을 가지치기.

예를 들어 첫번째 퀸을 (0,0)에 놨다면(그림 참고)

두번째 퀸을 (1,0) 또는 (1,1)에는 배치 할 수 없음.

이런 경우 세번째, 네번째 퀸이 어디로 배치되던 상관없이 실패 케이스이므로 가지를 쳐버리는 것.

즉 이후 단계에 퀸 배치가 불가능하다면 하위 트리를 아예 배제한다.

if is_ok_on(row):
    dfs(row + 1)

def is_ok_on(nth_row):
    """
    n번째(nth) 행에 퀸을 놓았을 때, 올바른 수인지 검사한다.
    nth 행의 퀸 위치와, 0번째 행부터 n-1번째 행까지 놓여진 퀸의 위치를 비교한다.
    nth 행에 놓여진 퀸이 규칙을 깼다면 False 를 반환한다.
    """
    # 0번째 행 ~ nth_row-1번째 행의 퀸 위치를 차례대로 꺼내온다.
    # 영상에서 n-1이라고 말하는데 오류입니다. nth_row-1까지 살펴봅니다.
    for row in range(nth_row):
        # 방금 놓여진 nth 퀸은 (nth_row, visited[nth_row]) 에 놓여져있다.
        # 각 행에 차례대로 단 한 번만 두기 때문에 행이 겹치는 것은 검사하지 않아도 된다.
        # 1) 열 번호가 겹치지는 않는지? visited[nth_row] == visited[row]:
        # 2) 또는 대각선으로 존재하지는 않는지? nth_row - row == abs(visited[nth_row] - visited[row]) 살펴본다.
        if visited[nth_row] == visited[row] or nth_row - row == abs(visited[nth_row] - visited[row]):
            return False
    return True

is_ok_on이라는 이 함수가 바로 가지치기의 역할을 하는 것.

열 번호가 겹치거나, 대각선에 존재하게 된다면 False를 반환하여 재귀 구조에서 빠져나오게 됨.

그렇지 않다면 True를 리턴받아 다음 dfs(row+1)를 진행하게 된다.

 

"""
visited 의 인덱스는 행, 값은 열을 나타낸다.
(1, 3)에 놓은 경우, visited[1] = 3 으로 표현하겠다는 것.

예시) n=4 이고 visited = [1, 3, 0, 2] 인 경우,
체스판을 그려보면 아래와 같다. (1이 퀸)
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
"""
visited = [-1] * n

코드에서 중요한 점은

당연히 이차원 배열이 필요할 것 같았지만 일차원으로 구성했다는 것.

어차피 한 줄에 퀸을 하나씩밖에 놓지 못하기 때문에 두 개의 지표가 필요 없다는 아이디어.

---

오늘의 회고

오늘은 복습 + 2주차 진도를 다 뺐다.

알고리즘 문제를 많이 못풀어서 조금 아쉬움.

 

내일의 목표는 2주차 복습(특히 DFS, BFS) + 오늘 못푼 스쿼드 문제 풀기