N-Queen

날짜 : 2023. 09. 13

사용 언어 : python

 

문제

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

 

코드

def dfs(row, depth):
    cnt = 0 # 개수 저장용
    if depth == len(row):  # 마지막 행까지 도달
        return 1
    for i in range(len(row)):
        row[depth] = i  # 해당 row에서 퀸을 위치시켰을 때
        for j in range(depth):
            if row[depth] == row[j] : break  # 같은 열인지 체크
            if abs(row[depth] - row[j]) == (depth - j): break  # 대각선인지 체크
        else: cnt += dfs(row, depth+1)   
    return cnt


def solution(n):
    row = [0] * n # 리스트 row의 i번째 값이 j -> [i][j]에 위치
    return dfs(row, 0)

 

 

풀이

- 일반 백트래킹처럼 2차원 배열로 설정해 대각선, 컬럼을 반복문으로 비교하면 TLE가 발생한다.

- 그래서 일차원 배열로 초기화한 후, 해당 인덱스를 row의 숫자, 그 원소값을 column으로 설정한 후 문제를 풀이한다.

- 그래서 depth와 길이가 동일한 경우는 모든 queen을 배치시켰다는 것으로 간주하기 때문에 카운트한 후 리턴

- 그 다음 해당 row(depth)에서 퀸을 놓았을 때의 케이스를 비교해 나간다.

- 첫 번째 if문은 같은 열인지 체크하는 것이기 때문에 리스트 row에서의 원소값을 비교한다.

- 그다음 if문은 대각선을 체크하는 조건문이다.

- 위 두개의 if문에서 동일한 경우는 위 열의 퀸과 만난다는 것을 보이기 때문에 해당 반복문을 탈출한다.

- 만약 걸리는 것이 없다면 다음 depth로 진행한다.

체크 방식

 

알게된 점

- 이전에 풀었던 N-Queen 문제와 동일해서 같은 풀이로 풀려고 했지만 꽤나 애를 먹었다.

- 일차적으로 대각선 풀이에서 어떻게 해 나가야 할 지 떠오르지 않아 많이 생각했던 것 같다.

- 다음은 마지막 테스트케이스에서 시간초과가 발생했다는 것이었는데, if문을 하나로 만들어서 비교했는데도 시간초과가 발생해 쪼개서 비교했고, 원래 만나는지 여부를 판별하기 위한 함수를 만들어서 보내는 방식으로 하려다가 그것도 시간초과가 발생해서 없애고 dfs 함수 하나에 다 넣어버렸다.

- 확실히 파이썬이.. 많이 느린거같긴 하다

 

 

참고 사이트

-