LV 2: N-Queen

문제 링크

LV 2: N-Queen

구현 방식

• 이전에 백준에서 풀었던 N-Queen 문제와 동일하다

• 프로그래머스에서 다시 풀 때 조금 억까였던게, dfs에서 다음 depth로 넘어가야할 지 말아야할 지를 판별하는 부분을 adjacent(r) 함수로 빼서 코드를 짜면 테케 11번에서 TLE을 받게된다
  -> 근데 그냥 함수 따로 안빼고 코드 짜서 돌리면 9656.93ms로 통과됨

코드

answer = 0
def solution(n):
    global answer
    
    # def adjacent(r):
    #     for i in range(r):
    #         if rows[i] == rows[r] or abs(rows[i] - rows[r]) == r-i: #같은 열이거나 대각선에 있는 경우 False 반환
    #             return False
    #     return True
    
    def dfs(depth):
        global answer
        
        if depth == n: # 성공
            answer += 1
            return
        
        for i in range(n):
            rows[depth] = i
            
            for r in range(depth):
                if rows[r] == rows[depth] or abs(rows[r] - rows[depth]) == depth - r: #같은 열이거나 대각선에 있는 경우 False 반환
                    break
            else:
                dfs(depth+1)

    rows = [0] * n #row당 queen의 column 위치
    dfs(0)
    return answer