[1스4코1파] #113. LV 2. N-Queen

[1스4코1파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 1명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (113일차)
[4코1파] 2023.01.13~ (104일차)
[1스4코1파] 2023.04.12~ (15일차)

Today :

2023.04.26 [113일차]

프로그래머스 LV 2
N-Queen
https://school.programmers.co.kr/learn/courses/30/lessons/159993

문제 설명

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

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

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

제한사항

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

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

문제 풀이 방법

풀이 방법? 구글링이다 이자식들아

내 코드

def dfs(queen, n, row):
    count = 0
    
    if n == row:
        return 1
    
    for col in range(n):
        queen[row] = col
        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)

증빙

다른 사람 풀이

첨 알게된 for-else 구문...
별도 board를 생성하지 않고 직선, 오른대각선, 왼대각선을 계산해서 관리하는 방법

여담

뭐 이딴 문제가 다있지..