[프로그래머스] N-Queen

1. 문제 설명

---

2. 풀이

---

• 가장 먼저 각 행에 몇번째 열에 퀸을 놓았는지 판단하기 위한 리스트를 생성해 dfs()메소드에 넣어줍니다.

#dfs(리스트,현재 행,n)
dfs([0]*n,0,n)

• 이 리스트와 DFS알고리즘을 사용하여 Queen을 놓을 위치를 탐색합니다.
• 만약 마지막 행까지 탐색했다면 탐색을 종료주는 예외처리를 합니다. (마지막행까지 탐색했을때 1개의 경우의 수가 생기므로 1을 반환합니다.)

if row == n:
    return 1

• 마지막 행이 아닌경우 현재 행 몇번째 열에 Queen을 배치할지 for문을 사용해 탐색합니다.

for col in range(n):
    queen[row] = col
    
    #배치가능한지 확인
    if is_valid(queen,row):    
        cnt+=dfs(queen,row+1,n)

• 이제 현재 배치한 행,열이 적합한 위치인지 판별해 줍니다.

for r in range(row):
    #같은 열에 위치한 퀸이 있는지 판단
    #같은 대각선 상에 퀸이 있는지 판단
    if queen[row] == queen[r] or abs(queen[row]-queen[r]) == row-r:
        return False
    return True

• 반환 결과가 True면 다음 행으로 진행하고 아니면 다른 열을 계속해서 탐색합니다.

3. 코드

---

def is_valid(queen,row):
    for r in range(row):
        if queen[row] == queen[r] or abs(queen[row]-queen[r]) == row-r:
            return False
    return True
def dfs(queen,row,n):
    cnt = 0
    if row == n:
        return 1
    
    for col in range(n):
        queen[row] = col
        
        if is_valid(queen,row):    
            cnt+=dfs(queen,row+1,n)
    return cnt
def solution(n):
    return dfs([0]*n,0,n)

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