N-Queen | Notion

백트래킹 예시문제

<aside> 💡 N-Queen (링크)

</aside>

N-Queen 문제 정리

Untitled

체스판의 크기인 N이 주어진다. (NxN) 체스판
퀸은 상하좌우 대각선 방향으로 움직일 수 있다.
각 행에 퀸을 놓을 수 있는 경우의 수를 반환한다.

N-Queen 문제 해설

먼저 위 그림처럼 2차원 배열을 1차원 배열로 만들어주는 아이디가 굉장했다.

아래처럼 1차원 배열로 생성하여 인덱스로 행을 값으로 열을 지정한다.
```
visited = [-1] * n
>>> [-1, -1, -1, -1]
```
경우의 수를 저장할 변수와 결과값을 저장할 변수를 생성한다.
```
count = 0
result = []
```
dfs라는 함수를 만들어 dfs방식으로 가지치기를 해나가도록 한다. 시작점을 넘겨준다.
```
dfs(0)
```

dfs함수

먼저 백트래킹할 반복 행동을 지정해준다.

넘겨받은 각 행에서 모든 열에 퀸을 배치하도록 한다. 여기서 is_ok_on이라는 함수는 퀸이 해당 열에 배치해도 될지 알려주는 함수로 아래에서 알아보자. is_ok_on을 통과하면 퀸이 해당열에 있어도 된다는 의미로 다음 행으로 넘어가도록 한다.
```
# 각행에서 열을 반복하여 배치.
    for col in range(n):
        visited[row] = col  # 퀸을 배치한다. (row, col)위치에
        if is_ok_on(row):  # 만약 자리에 놔도 된다면
            dfs(row + 1)  # 다음 행으로 이동한다.
```

다음으로 종료 조건을 지정해준다.

모든 행에 퀸을 배치했을 경우 n(맵의크기)가 row(행의크기)와 같아졌을 때이다.

이 때, 1차원 배열인 visited를 통해 2차원 배열을 생성한다.

# 모든 행에 퀸을 배치했을 때.
# 그리드 그리기
if row >= n:
    nonlocal count  # 지역변수가 아니라는것을 의미
    count += 1      # 경우의 수 업데이트
    #그리드 그리기
    grid = [['.'] * n for _ in range(n)]
    for idx, value in enumerate(visited) :
        grid[idx][value] = 'Q'
    answer = []
    for row in grid :
        answer.append(''.join(row))
    result.append(answer)
    return

퀸 배치 판별 알고리즘

is_ok_on은 앞서 열에 퀸을 배치했을때, 아래 조건들을 판별한다.

(1) 다른행의 열이 겹치는지

(2) 다른행의 대각선에 겹치는지

def is_ok_on(nth_row):
        # 0번째 행에서 현재까지의 행 이전까지를 불러온다.
        for row in range(nth_row):
            # (1) 열이 겹치는지 판단.
            # visited[nth_row] -> 현재 행의 퀸의 위치
            # visited[row] -> 이전 행의 퀸의 위치
            # (2) 대각선으로 겹치는지 판단.
            # x좌표값의 차이 - y좌표값의 차이가 같으면 대각선으로 겹치는 것
            # 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