[프로그래머스] N-Queen

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

코드 1 - 실패

def fill(board, n, y, x):
    dy = [1, 1, -1, -1]
    dx = [1, -1, 1, -1]
    
    for i in range(n):
        board[i][x] = 1
        board[y][i] = 1
        
        for d in range(4):
            ny = y + dy[d] * i
            nx = x + dx[d] * i
            if 0 <= ny < n and 0 <= nx < n:
                board[ny][nx] = 1

def solution(n):
    answer = 0
    
    for s in range(n):
        board = [[0] * n for _ in range(n)]
        count = 1
        print()
        fill(board, n, 0, s)
        
        for y in range(1, n):
            for x in range(n):
                if board[y][x] == 0:
                    fill(board, n, y, x)
                    
                    count += 1
        if count == n:
            answer += 1
    
    return answer

만들다가 만 코드이다. 처음에 문제 이해를 잘 못해서 그냥 최초에 빈칸 만나는 경우마다 퀸을 두도록 하는 코드로 만들어버렸다. 당연하게도 실패했다.
빈 칸에 두고 경우 확인하고 다시 새로운 빈 칸에 두는 경우를 생각해봤는데 지금 코드로 안 될 것 같아서 쓰다가 말았다.

코드 2 - 시간초과

def check(x, row):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True

def dfs(x, n, row):
    if x == n:
        return 1
    else:
        answer = 0
        for i in range(n):
            row[x] = i
            if check(x, row):
                answer += dfs(x + 1, n, row)
        return answer


def solution(n):
    answer = 0
    row = [0] * n
    return dfs(0, n, row)

DFS로 해결했다. row의 index가 y좌표, row[x]가 x좌표가 되도록 설정했고, 같은 대각선에 있는 점은 y, x값의 차가 같다는 것을 이용해서 검증했다.

그런데 이렇게 하니까 12이상의 수에서 시간초과가 발생했다. 백준에는 pypy3이 있어서 그걸로 하니까 돌아가던데 프로그래머스는 실패다.

코드 3

메모이제이션을 사용하기로 했다.

체스판의 대각선 개수는 한쪽방향만 따졌을 경우 2*n - 1이다.
/ 방향을 생각했을 때 0번 index는 1칸, 1번은 2칸, 2번은 3칸, 3번은 4칸 이런식으로 해서 총 7개의 대각선을 가지고 반대 방향도 마찬가지이다.
이것을 활용해서

diagonal1 = [False] * (2 * n -1)
diagonal2 = [False] * (2 * n - 1)

이렇게 두 방향의 대각선이 visited인지 판단할 리스트 두 개를 생성해준다.

diagonal1을 "/" 방향이라고 생각하고 접근을 시작하면 y + x가 일정한 점이 된다. 리스트가 x축으로 뒤집힌 1사분면이라고 생각하면 y+x=c라는 직선 상의 점이 된다.

diagonal2를 반대 방향이라고 생각하면 y=x+c의 직선상의 점이 되는데 이는 즉 y-x - c = 0가 된다. 여기서 c는 y가 0~n-1, x도 0~n-1이고 y>=x이기에 0부터 시작하기 위해서 c는 n-1로 설정해주면 된다.

마지막으로 같은 열에 있는 것을 탐지하기 위해서 row[x]가 false인 점만 찾아다니면 된다.

def solution(n):
    
    row = [False] * n
    diagonal1 = [False] * (2 * n - 1)
    diagonal2 = [False] * (2 * n - 1)
    
    def dfs(y):
        if y == n:
            return 1
        answer = 0
        for x in range(n):
            if not row[x] and not diagonal1[y + x] and not diagonal2[y - x + n - 1]:
                row[x] = diagonal1[y+x] = diagonal2[y-x+n-1] = True
                answer += dfs(y+1)
                row[x] = diagonal1[y+x] = diagonal2[y-x+n-1] = False
        return answer
    
    return dfs(0)