프로그래머스 N-Queen (python, 파이썬)

• 문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

---

• 제한 사항
  • 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
  • n은 12이하의 자연수 입니다.

---

• 입/출력

n	result
4	2

---

• 코드

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)

먼저 queen 배열은 각 index가 row이고 해당 value가 column이라고 생각하면 될 것 같다.

예를들어, [1, 3, 0, 2]라면 [0, 1], [1, 3], [2, 2], [3, 2]에 queen이 배치되어있다.

 

이후 각 row에는 하나의값만 들어가기 때문에 이렇게 편하게 list로 만들수있다.

하나의 값을 넣고 queen[row] = col 그 이후에, 세로로도 겹치면 안되기 때문에 지금까지의 queen배열의 같은 값이 있는지 확인을 하고 있다면 break로 탈출한다.

또한 queen은 대각선으로도 이동이 가능하기 때문에 해당 col의 차이가 row의 차이와 같다면 대각선으로 이동이 가능하기때문에 break로 탈출한다.

 

여기서 중요한 구문이 나온다. 만약 break로 탈출하지 않은 경우에만 for-else구문을 활용해서 else로 넘어가게된다. 즉 가로는 겹치지않게 만들었고 세로랑 대각선으로 겹치지 않는다면 dfs로 이어서 진행을 하는것이다.

 

count변수를 넣어서 row가 n 즉, 끝까지 도달했다면 값을 추가하고 종료해주고 아니라면 count=0에서 return이 되어서 0이되게된다.

 

---

• 출처

programmers.co.kr/learn/courses/30/lessons/12952?language=python3