#9663

처음 짰던 코드

N = int(input())

chessMap = []
dontGoMap = []
totalCnt = 0
# print(chessMap)

def clearChessMap():
    chessMap.clear()
    chessMap = [ [0] * N for i in range(N)]

def clearDontgoMap():
    dontGoMap.clear()
    dontGoMap = [ [0] * N for i in range(N)]

def markingDontGoMap(row, col):
    # 못가는 곳(퀸 놔둘 수 없는 곳) 전부 체크
    for i in range(N):
        for j in range(N):
            if i == row:
                dontGoMap[i][j] = 1
                # 가로
            if j == col:
                dontGoMap[i][j] = 1
                # 세로

            # 대각선은? 
    
def dfs(queenCnt, row, col):
    if queenCnt == N:
        # queenCnt => 현재 퀸의 개수
        totalCnt += 1
        return
        # 퀸 다 놔뒀으면 리턴

    if dontGoMap[row][col] == 0:
        chessMap[row][col] = 1
        queenCnt += 1
        # 전달 받은 위치에 퀸 하나 넣어, 현재 퀸의 개수(queenCnt) += 1

        markingDontGoMap()
        # 못가는 곳 체크
    
    for i in range(N):
        for j in range(N):
            dfs(queenCnt, i, j)

    clearChessMap()
    chessMap[i][j] = 1
    markingDontGoMap()

dfs(0, 0, 0)
print(totalCnt)

이렇게 돌리면 시간이 안넘치나? 라는 생각을 어느 정도 하고 있었다.

가지 못하는 곳을 체크하는 도중에 대각선은 어떻게 체크해줘야 하지? 라는 의문이 들어서 이 부분만 구글에 검색해보고 힌트를 얻어야겠다 라는 생각을 했다.

접근 방식은 비슷했지만 이렇게 풀면 안된다는 걸 알았고 다시 풀기 시작했다. 이 문제 정말 어렵다. 생각지도 못했던, 답지를 보기 전까진 절대 몰랐을 접근 방식이 너무 많이 나왔다.

문제의 핵심

이 문제의 핵심을 파고드는 가장 첫 번째 힌트가 굳이 못가는 곳을 다 체크할 필요가 없다 라는 사실이다.

답지에서는 1차원 배열을 이용해 퀸의 위치를 파악하고 이를 이용해 못가는 곳을 체크한다. (나는 2차원 배열을 하나 더 만들어서 퀸의 위치가 정해질 때마다 못가는 곳을 전부 마킹해주려고 했다. 이것부터가 말이 안됐던 것이다.)
=> N이 최대 15니까, 1515 사이즈의 2차원 배열을 1515번 만큼 돌면서 15*15짜리 배열을 계속 마킹해줘야 하는건가? 아무튼 말이 안된다.

해설, 즉 답지의 풀이 방법은 생각보다 매우 간단했다. 1차원 배열에 인덱스 값을 로우 인덱스, 그 값을 컬럼 인덱스 라고 매핑해주면 된다. 그러면 1차원 배열로 퀸의 위치를 표현 가능하다.

이게 가능한 이유가 무조건 로우 하나당 퀸이 하나만 있다는 전제 때문이다.

예를 들어. [0, 2, 4, 5] 라고 하면

[0][0] , [1][2], [2][4], [3][5] 에 퀸이 있는 것이다.

for i (0 ~ 컬럼 길이) 하면서 해당 로우의 컬럼을 하나씩 차례대로 돈다. 로우당 무조건 퀸은 하나 이므로 해당 로우에서 퀸의 위치가 지정되면? (놔둘 수 있는 자리이면) 다음 로우에서 컬럼 별로 또 돌면 된다. 여기서 만약 모든 컬럼을 다 돌았는데도 놔둘 자리가 없으면 다시 이전으로 (바로 위의 로우) 가서 옆에 컬럼을 확인하면 된다. (재귀의 탈출)

로직은 바로 이해가 됐다. (물론 row 별로 무조건 퀸이 하나여서 로우 단위로 돌면 된다는 건 몰랐다. 몇시간을 머리 박아도 절대 몰랐을 것이다.

또 한가지 중요한 키 포인트가 바로 해당 로우에서 해당 컬럼의 차례가 왔을 때 그 자리가 퀸을 놔둘 수 있는 자리인지 체크하는 로직인데 답지를 보기 전에도 그랬지만 도대체 대각선을 어떻게 체크하는 지를 도저히 모르겠더라

이것도 의외로 간단했다. 그냥 예를 하나 잡아서 직접 값을 보면 된다.

예를 들어 현재 퀸의 위치가 (3, 3)라고 가정 왼쪽 대각선의 좌표는 각각 (2, 2), (1, 1), (0, 0) 이고 (3, 3)과 각각의 좌표들 차이는 모두 같다. (1로 같고, 2로 같고, 3으로 같다)

오른쪽 위 대각선 값들을 확인, 오른쪽 대각선의 좌표는 (2, 4), (1, 5), (0, 6) 이므로
마찬가지로 (3, 3)과의 좌표 차이는
(3,3) 이랑 (2, 4) => 1, -1
(3,3) 이랑 (1, 5) => 2, -2
(3,3) 이랑 (0, 6) => 3, -3

따라서

abs(graph[x] - graph[i]) == abs(x - i) 

이라는 조건문이 나온다.

최종 퀸의 위치 확인 코드는

for i in range(x):
    # 0부터 건네받은 로우까지 볼거야

    if graph[x] == graph[i] or abs(graph[x] - graph[i]) == abs(x - i):
        return False

return True

1. 건네 받은 로우 값의 컬럼 값이랑 0부터 지금까지 로우 돌면서의 컬럼 값이 같은지 확인, 같다면? => 같은 컬럼에 못놔둔다

2. 대각선에 놔둘 수 있는지 => 대각선에 있으면 그 컬럼에 못놔둔다.
   

퀸을 맨 위의 로우부터 아래로 가면서 채우고 있으므로 대각선을 확인할 때 현재 i보다 큰 값들은(아래 부분) 확인할 필요가 없다.
=> 밑에 부분은 어차피 밑의 로우를 볼 차례가 됐을 때 위로 다시 확인을 할거기 때문에
=> 이것도 진짜 신박하다. 너무 당연한데 절대 몰랐다.

최종 코드

N = int(input())

graph = [0] * N 
totalCnt = 0

def canFix(x):
    # x 는 로우 값

    for i in range(x):
        # 0부터 건네받은 로우까지 볼거야

        if graph[x] == graph[i] or abs(graph[x] - graph[i]) == abs(x - i):
            return False

    return True
    
    
def dfs(queenCnt):
    global totalCnt

    if queenCnt == N:
        # queenCnt => 현재 퀸의 개수, 현재 로우의 위치 => 이게 이 문제의 핵심!!!

        # queenCnt == N 이라는 말은 퀸 다 채웠고, 현재 젤 마지막 로우를 채우고 그 다음번에 왔다 라는 걸 의미

        # 사실 대각선을 체크하는 것도.. 중요해 보이지만 저건 어떻게 생각해낼 수가 있나? 다른 문제에서도 쓸 수 있을까 라는 생각을 했다.
        # 일반적이지 않은 조금은 기상천외하다? 라고 느꼈다

        totalCnt += 1
        return
        # 퀸 다 놔뒀으면 리턴
    
    # 해당 로우로 왔어. 
    # 컬럼별로 돌아야지 놔둘 때가 있는지
    else:
        for i in range(N):
            # N 번째 컬럼까지 볼거야
            
            graph[queenCnt] = i
            # queenCnt 이 지금 몇번째 로우 인지 가르쳐 주는 거야
            # i는 몇번째 컬럼인지

            # 그래서 바로 위 코드는? [queenCnt][i] 에다가 퀸을 놓겠다 가 되는거지

            if canFix(queenCnt):
                # 만약 지금 퀸을 놓을 위치가 되는 위치라면 다음 로우로 넘어가
                dfs(queenCnt+1)

        # 만약에 안됐어 그럼 => graph[queenCnt] = i
        # 바로 다음 컬럼 값으로 갱신하고 다시 확인하겠지 => visitMap 을 만들어줄 필요가 없다. 
        # 어차피 컬럼값이 갱신되면서 다음 컬럼 에다가 퀸을 놔둘 수 있는지 보거든

dfs(0)
# 여기서 제일 처음 호출하는 0은? 0번째 로우를 말하지
print(totalCnt)

for 문을 돌기 전에 (컬럼별로 확인해보기 전에) else를 적어주지 않으니 시간초과가 뜨더라

이게 무슨 상관인지 아직도 모르겠다.

어차피 if 에서 return 이 안되면 아래 for문으로 오는 건 똑같지 않나? 왜 else가 있고 없고에서 시간 초과인지와 아닌지 차이가 있는 건지 모르겠다.