[SWEA] D3. N-Queen

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=2 

SW Expert Academy

 

 

1. 해결방법

알고리즘 공부 초기에 백준에서 쓴맛을 봤던 문제인데 여전히 이해가 잘 안가고 혼자서는 풀진 못했다. 
아무래도 시간복잡도에 대한 고려도 해야되다보니 2차원 배열을 사용하지 않고 행을 초기화 함으로써 코드를 짜야하는 것이 막혔던 것 같다. 행 하나하나를 초기화하고 체크하다보니 아이디어도 막혀버려서 다른 분들의 풀이를 도움 받고 완전히 이해했다.
혼자서 2시간 삽질함,,

위의 그림을 보고 간신히 이해했다.... 감사합니다

 

 

2. 정답코드

# dfs
def dfs(check, num):
    global answer

    if num == N:
        answer += 1
        return

    maps = [0] * N
    for i in range(len(check)):
        # 열
        maps[check[i]] = 1

        # 오른쪽 대각선
        if check[i] + (num - i) < N:
            maps[check[i] + (num - i)] = 1

        # 왼쪽 대각선
        if check[i] - (num - i) >= 0:
            maps[check[i] - (num - i)] = 1

    for i in range(N):
        if maps[i] == 0:
            check.append(i)
            dfs(check, num + 1)
            check.pop()


T = int(input())
# T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())

    answer = 0
    chk = []

    dfs(chk, 0)
    print(f"#{test_case} {answer}")

 

 

 

 

 

[참고]

https://rheem-hm.tistory.com/60