[프로그래머스] N-Queen, 파이썬

💡 문제 해결 아이디어

내가 생각한 아이디어

• 이건 어쩔 수 없는 완전탐색 문제라고 생각했다. 모든 방법의 수를 찾아야하니까
• DFS를 이용한 백트래킹으로 다 찾아내야겠다고 생각했으나...
• 실수 : 굳이 체스판을 2차원 배열로 구현하려고 했었고, 이는 굉장히 비효율적이었다.

🛠 피드백 아이디어

• 그냥 이전 행(또는 열)들에서 어떤 열(또는 행)에 Queen을 뒀는지 기록하기만 해도 충분했다!

💻 작성된 코드

def solution(n):
	# 어태까지의 queen 위치 ls, 내가 두려는 위치 new
    def check(ls, new):
        for i in range(len(ls)):
        	# 같은 열에 퀸을 둔 적이 있거나, 대각 위치에 둔 적이 있다면, return False
            if new == ls[i] or (len(ls)-i) == abs(ls[i]-new):
                return False
        return True
    def dfs(n, ls):
    	# 끝 행까지 도달! return 1
        if len(ls) == n:
            return 1
        # 끝 행이 아니라면, 다음 줄을 다시 탐색
        cnt = 0
        for i in range(n):
            if check(ls, i):
                cnt += dfs(n, ls+[i])
        # 탐색 결과를 return
        return cnt
        
    return dfs(n, [])