[Level 2] / [Python] N-Queen

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

프로그래머스

---

접근 방법

DFS 중 불가능 한 부분을 더이상 탐색하지 않고 바로 다음 단계를 탐색하는 방법인 백트래깅을 사용합니다.

---

실패한 코드

한 곳을 탐색하고 다른 곳을 탐색하지 못하였고

그리고 구성 자체부터 잘못 되었습니다.

def solution(n):
    answer = []
    
    def DFS(y, x):
        check = [[y, x]]
        maps[y][x] = 1
        for r in range(n):
            for c in range(n):
                nx, ny = c, r
                if ny == y or nx == x or abs(ny - y) == abs(nx - x):
                    continue
                if ny >= n or nx >= n:
                    continue # check
                
                isin = False
                for c in check:
                    if c[0] == ny or c[1] == nx or abs(c[0] - ny) == abs(c[1] - nx):
                        isin = True
                        break
                    else:                        
                        isin = False
                
                if isin == False:
                    maps[ny][nx] = 1
                    check.append([ny, nx])          

        return check 
    map_list = list()
    for r in range(n):
        for c in range(n):
            maps = [[0 for _ in range(n)] for _ in range(n)]
            ch = DFS(r, c)
            
            if len(ch) == n and ch not in answer and maps not in map_list:
                map_list.append(maps)
                answer.append(ch)    
    return len(map_list)

---

다른 사람 풀이

결국 다른 사람의 풀이를 참고하였습니다.

한 행에 하나의 퀸만 있을 수 있다는 점을 사용하여 1차원 배열로 표현하였습니다.

그리고 세로에 있을 경우, 대각선에 있을 경우를 배제하며 DFS로 탐색을 진행합니다.

def dfs(queen, n, row):
    count = 0
    
    if n == row:
        return 1
    
    # 가로로 한번만 진행
    for col in range(n):
        queen[row] = col
        # for-else구문
        for x in range(row):
            # 세로로 겹치면 안됨
            if queen[x] == queen[row]: 
                break
                
            # 대각선으로 겹치면 안됨
            if abs(queen[x]-queen[row]) == (row-x):
                break
        else:
            count += dfs(queen, n, row+1)
            
    return count

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