BAEKJOON 15649, 15650, 15651, 15652

21 Jan 2020

15649 문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

---

나의 처음 코드

n = int(input())

row_list = [] #행
col_list = [] #열

#들어갈 수 있는 좌표인지 체크하는 함수
def check_valid(coord : tuple):
    row = coord[0]
    col = coord[1]
    tmp_row = 0
    tmp_col = 0
    #퀸이 들어가 있는 좌표의 행과 열이 같다면 들어갈 수 없다.
    if (row in row_list) or (col in col_list):
        return False
        #퀸이 들어가 있는 좌표의 대각선 좌표에 존재한다면 들어갈 수 없다.
    for i in range(len(row_list)):
        tmp_row = abs(row_list[i] - row)
        tmp_col = abs(col_list[i] - col)
        if tmp_row == tmp_col:
            return False
    return True

def n_queen(depth : int):
    global num_of_case
    #한 행에 무조건 하나의 퀸이 들어가야하므로 탈출 조건은 다음과 같다.
    if depth == n:
        num_of_case += 1
        return
    #재귀부분
    for i in range(0, n):
        if depth == 0 or check_valid((depth, i)):
            row_list.append(depth)
            col_list.append(i)
            n_queen(depth+1)
            row_list.pop()
            col_list.pop()
    return num_of_case

num_of_case = 0
print(n_queen(0))

결과는 정답입니다. 단, Pypy3 에서 돌리지 않고, Python3에서 돌리면 시간초과가 난다. 다른 사람들도 대부분 Pypy3로 돌렸다. 위의 코드 경우, 26164ms 가 나오는데 56ms가 나온 코드가 있다. 어처구니 없으니 준비하길 바란다.

print([1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596][int(input())-1])

정답을 써놓고, 정답만 추출하는 식의 코드이다. 다행히 입력하는 값들이 적어서 다행이지 많으면 안되는 코드일 것이다. 위의 코드에서 한가지 배울점은,

print([list][index]) #이렇게 쓰면 list의 index가 가지고 있는 값이 출력된다는 것이다. 한줄로 간편히 쓸 때 편하다.

백트래킹하면 무조건 나오는 문제인만큼, 한번 꼭 풀어보길 바란다.