프로그래머스 [Lv. 2] N-Queen {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

def solution(n):
    answer = [0]
    visited = [[0 for _ in range(n)] for _ in range(n)]
    
    def isValid(r, nc):
        for i in range(n):
            if visited[i][nc]:
                return False
        
        #좌각선, 우각선
        for j in range(r-1, -1, -1):
            if nc-r+j >= 0 and visited[j][nc-r+j]:
                return False
            if nc+r-j < n and visited[j][nc+r-j]:
                return False
        
        return True
    
    def dfs(r, c, cnt):
        if r == n:
            answer[0] += 1
            return
        
        for nc in range(n):
            if not isValid(r, nc):
                continue
            visited[r][nc] = 1
            dfs(r+1, nc, cnt+1)
            visited[r][nc] = 0
        
    for i in range(n):
        visited[0][i] = 1
        dfs(1, i, 1)
        visited[0][i] = 0
        
    return answer[0]

풀이 방법

1. 가장 위에 있는 행부터 퀸을 놓을 수 있는지 isValid로 확인한다.
   1. isValid는 상하와 좌각선 우각선을 확인한다.
   2. 유효하면 퀸을 둔다.
2. r이 n에 도달했다는 말은 유효한 체스판이므로 answer += 1을 해준다.
3. answer를 반환한다.

느낀점

• 혼자서 못 풀었던 문제 같은데 드디어 풀었다.