백트래킹, N-Queen

Why?

• 필요없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법을 백트래킹이라고 한다.
• DFS, BFS를 처럼 완전탐색을 할 때, 효율적으로 만들어주는 기법이다.
• 볼 필요가 없는 수는 보지 않음!
• 예를 들어 DFS를 할 때, 조건문으로 이미 탐색한 노드나 탐색이 필요 없는 노드를 만나면 return 해버림
• 대표적인 문제 N-Queen이 있다

N-Queen

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

• N*N 체스판에 N개의 퀸을 배치할 수 있는 경우의 수를 센다.
• 퀸은 상하좌우, 대각선 방향으로 거리 제한 없이 이동할 수 있다.
• 위 그림을 예로들면 4개의 퀸을 놓으면 각각의 행 과 열에 하나씩 놓인다. 
• 만약 두개의 퀸이 같은 열에 있으면 서로 잡아먹을 수 있기 때문이다! 행이나 열이 겹치면 안된다!
• 그리고 같은 대각선에 놓여있어도 안된다!
• N=8인 경우, 경우의 수는 다음과 같다. 
  • 64 * 63 * ... * 57 = 178,462,987,637,760
  • C 기준 1초에 1억 번을 연산하므로 모든 경우의 수를 탐색하는데 약 20.6시간이 소요된다.

count = 0

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

# row번째 행에 퀸을 두는 행동을 함
# dfs(n-1) n-1번째 행에서의 퀸을 두는 행동!
def dfs(row, visited):
    # n이 되었다는 것은 모두 올바른 위치에 퀸을 두었다는 의미!
    global count
    if row == len(visited):
        count += 1
        return
    # visited[row]의 값을 정한다다
    for col in range(len(visited)):
        # n행에서 col열에 퀸을 둔다
        visited[row] = col
        if is_Ok(row, visited):
            dfs(row + 1, visited)

def solution(n):
    # 2차원을 나타내려면 2차원 배열이 필요할거라 생가각하지만
    # 각 행당 하나씩밖에 퀸을 못두고
    # 두개의 열의 정보가 나오지 않으니까 1차원 배열로
    # 2차원 좌표값을 나타낼 수 있다
    # n = 4 이고 visited가 [1, 3, 0, 2]인 경우,
    # 체스판을 그려보면 아래와 같다!
    # 0 1 0 0
    # 0 0 0 1
    # 1 0 0 0
    # 0 0 1 0
    # 즉 visited의 행은 인덱스이고 열은 해당 인덱스의 값이다
    visited = [-1] * n
    dfs(0, visited)
    return count