[python] 프로그래머스 - N-Queen

🤔문제 해결

Lv3 | 백트래킹, DFS

 

규칙은 체스말의 좌우, 위아래, 대각선 모두 겹치지 않게 하는 것이다!

3번 째 행에서 더 이상 말을 둘 수 없다.

4번째 행에서 더 이상 말을 둘 수 없다.

성공!

하지만 모든 규칙을 하나하나 체크하면 효율성 마지막에서 시간초과가 발생한다!

• 위아래 규칙: visited 리스트를 만들어서 세로(열) 한칸에 하나씩만 들어갈 수 있게 한다.
• 좌우 규칙: 한번 말을 놓으면 무조건 다음 행으로 넘어간다.
• 대각선 규칙: 말을 놓을 준비를 하고, 그 자리의 왼쪽 위대각선과, 오른쪽 위대각선에 말이 있는지 체크!

마지막 행까지 말을 둘 수 있으면 성공!

 

💨

 

💻소스 코드

def solution(n):
    answer = 0
    chess = [[0] * n for _ in range(n)]  # 체스판
    visited = [0] * (n + 1)  # 세로칸 방문 체크

    # 조건에 일치 하는 지 체크 | 왼쪽 대각선, 오른쪽 대각선
    def check(x, y):
        ly, ry = y, y
        while x >= 0:
            x -= 1
            ly -= 1
            ry += 1
            if 0 <= ly:  # 왼쪽 대각선
                if chess[x][ly]:
                    return False

            if ry < n:  # 오른쪽 대각선
                if chess[x][ry]:
                    return False

        return True

    def bt(idx=0):
        nonlocal answer
        if idx == n:  # 체스를 마지막칸까지 두는데 성공한 경우
            answer += 1
            return

        for i in range(n):
            if visited[i] == 0:  # 세로 칸에 둔 말이 없는 경우
                if check(idx, i):  # 대각선방향 체크
                    chess[idx][i] = 1  # 체스판에 말을 두고
                    visited[i] = 1  # 이제 i 칸(세로 전체)는 말을 못둔다.
                    bt(idx + 1)
                    chess[idx][i] = 0
                    visited[i] = 0

    bt()

    return answer

 

📕문제 확인

출처: 프로그래머스

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

코딩테스트 연습 - N-Queen

 

---

문제 설명

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

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

 

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

제한사항

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

---

입출력 예

nresult

4

2