[3주차 - Searching] N-Queen

본 포스팅은 프로그래머스 에서 진행하는 코딩테스트와 실무역량 모두 잡는 알고리즘 스터디(Python반) 6기에 참여 하면서 공부한 내용을 정리한 것이다. (https://programmers.co.kr/learn/courses/12441)

 

상단부터 

1. [문제설명] 
2. [문제풀이] 
3. [코드 리뷰를 통해 발견한 개선할 점] 
4. [리뷰완료 후 전체코드] 

순으로 구성되어 있다.

---

[문제설명]

N-Queen

가로, 세로 길이가 n인 정사각형으로 된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인 경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한 번에 공격할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족하도록 배치할 수 있는 방법의 수를 return 하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12 이하의 자연수입니다.

---

입출력 예

nresult

4

2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

---

[문제풀이]

우선 이 문제가 back tracking 문제라는 것을 모르는 상태에서 완전탐색으로 접근했다.

1. n x n 좌표계를 만들고 모든 좌표들 가운데 n개씩 취하는 조합을 튜플형으로 만들어 퀸을 배치할 수 있는 모든 경우의 수를 담은 리스트를 작성한다.

2. 각 후보들에 대해 후보 안에 있는 좌표 정보들을 바탕으로 좌표 간에 수직, 수평, 대각선 공격 가능 여부를 파악하여 공격이 불가능할 경우에 대해서만 해당 튜플을 별도의 set에 넣어준다.

3. 모든 후보들에 대해 2번을 반복한다.

4. 공격하지 못하는 좌표들을 담은 set의 길이를 리턴한다.

 

하지만 이렇게 접근할 경우 n = 12 이면 순열의 수 공식에 의해 (nPr = n! / r! * (n - r)!) 144! / 12! * (144 - 12)! 나 되는 머릿속이 아득해질 정도의 데이터를 처리해야 한다. 코딩테스트에서 허용하는 연산 시간이 1 ~ 5초이므로 가장 크게 5초로 잡아도 완전탐색으로는 n = 6이 제한 시간 내에 처리할 수 있는 한계이다. 즉, 이 풀이는 시간 초과로 오답 처리된다.

def solution(n):
    answer = 0

    # n x n 체스판 상에 배치될 수 있는 모든 퀸의 위치를 생성하여 4개 씩 조합을 만들어 낸다.
    coordinates = list()
    for i in range(n):
        for j in range(n):
            coordinates.append((i, j))
    queen_coordinates = list(combinations(coordinates, n))

    # 공격할 수 없는 좌표 모음 수를 카운트 한다.
    can_not_be_executed = set()
    for queen_coordinate in queen_coordinates:
        is_executable = False
        for point in queen_coordinate:
            for other_point in queen_coordinate:
                # 수평방향으로 동일 선상에 공격 가능한 대상이 있는지 확인한다.
                if point != other_point and point[0] == other_point[0]:
                    is_executable = True
                    break
                # 수직방향으로 동일 선상에 공격 가능한 대상이 있는지 확인한다.
                if point != other_point and point[1] == other_point[1]:
                    is_executable = True
                    break
                # 대각 4방향으로 동일 선상에 공격 가능한 대상이 있는지 확인한다. (기울기가 1이면 대각상에 위치한 것)
                if point != other_point:
                    slope = abs((point[1] - other_point[1]) / (point[0] - other_point[0]))
                    if slope == 1:
                        is_executable = True
                        break
            if not is_executable:
                continue
        # 공격 가능한 지점이 없으면 can_not_be_executed 1증가
        if not is_executable:
            can_not_be_executed.add(queen_coordinate)
    answer = len(can_not_be_executed)
    return answer

 

 

n-queen은 3주 차 문제 중 유일하게 자력으로 풀지 못한 문제인데, 나중에 검색해보고 알았지만 유명한 back tracking 알고리즘 문제였다. back tracking을 모르니 풀지 못할 수밖에...

 

back tracking은 DFS등으로 완전탐색을 진행하면서 더 이상 확인할 필요가 없는 가지를 미리 판단하여 탐색하지 않는 알고리즘이라 생각하면 된다.

 

이제 back tracking 알고리즘을 적용해 보자.

1. 첫 번째 row의 첫 번째 column부터 queen을 배치한다.
2. 두 번째 row에 queen을 배치하되 두 가지를 고려하여 배치한다.
   • 이전 row에 먼저 놓인 queen과 동일한 column에는 놓지 못한다.
   • 이전 row에 먼저 놓여진 queen과 대각선 상의 위치에는 놓지 못한다.
3. 배치하다가 마지막 row까지 배치하지 못하고 더 이상 배치할 수 있는 방법이 없는 경우 이전 row로 되돌아가 다음 배치할 수 있는 곳을 찾아 배치한다.
4. 마지막 row까지 queen을 배치한 경우 서로 공격할 수 없는 위치를 하나 찾은 것이다.

위의 내용을 바탕으로 처음 작성한 코드는 다음과 같다.

global_count = 0
def n_queens(row, column, N, set_columns):
    # 모든 행에 대해 각각 놓을 수 있는 위치를 찾았다면 공격할 수 없는 위치를 찾은 것이다.
    if row >= N - 1:
        global global_count
        global_count += 1
        return True
    # 다음 행에 놓을 위치를 결정한다.
    for next_column in range(N):
        if next_column != column - 1 and next_column != column + 1 and next_column != column and \
                next_column not in set_columns:
            is_on_diagonal = False
            for i in range(len(set_columns)):
                # (next_column, row + 1) -> next position
                # (set_column[i], i) -> 비교해야할 기존 좌표.
                if abs((row + 1) - i) / abs(next_column - set_columns[i]) == 1:
                    is_on_diagonal = True
            if not is_on_diagonal:
                set_columns.append(column)
                n_queens(row + 1, next_column, N, set_columns)
                set_columns.pop()



def solution(N):
    count = 0
    for i in range(N):
        n_queens(0, i, N, [])
    return global_count

---

[코드리뷰를 통해 발견한 개선할 점]

1. 재귀 호출 시에 데이터 흐름을 따라가기 힘들어 전역 변수를 썼는데, 전역변수의 사용은 코드 변경에 따라 치명적인 실수를 유발할 수 있고 실행 속도 면에서도 느리므로 특별한 경우가 아니고는 사용을 지양하는 것이 좋다.

 

전역변수를 제거하고 개선한 코드는 아래와 같다.

---

[코드리뷰 완료 후 전체 코드]

def n_queens(set_columns, row, n):
    total_count = 0
    #  첫번째 row의 0 ~ n - 1 column이 각각의 시작점이다.
    for col in range(n):
        # 다른 퀸의 위치를 감안하여 놓을 수 있다면
        if confirm_pos(set_columns, row, col):
            # set_columns에 현재 퀸을 놓은 위치를 저장한다.
            set_columns[row] = col

            # 마지막 row까지 도달한 경우 total_count를 1 증가 시킨다.
            if row == n - 1:
                total_count += 1
            # 마지막 row가 아니면 row를 1증가시켜 DFS 진행한다.
            else:
                total_count += n_queens(set_columns, row + 1, n)

    return total_count


# (row, col)에 퀸을 놓을 수 있는지 확인한다.
def confirm_pos(set_columns, row, col):
    for r in range(row):
        # 같은 column 상에 퀸이 있으면 False
        if set_columns[r] == col:
            return False
        # 모든 row을 순회하며 이미 놓여진 퀸이 있는 경우
        # (row, col)에서 (r, set_columns[r])까지의 가로축 변화량과 세로축 변화량이 같으면 대각선 상에 위치한 것으로 False
        if (row - r) == abs(col - set_columns[r]):
            return False
    return True


def solution(n):
    set_columns = [0] * n
    return n_queens(set_columns, 0, n)