2806. N-Queen (코딩테스트, SW Expert Academy)

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB 

SW Expert Academy

나의코드 (걸린시간: 43분 34초)

def diag(table,size):#가능한 위치를 리스트화 시켜 리턴
    target = []
    left = [i+table[i] for i in range(len(table))] # 첫번째 대각선 종류
    right = [-i+table[i] for i in range(len(table))]# 두번째 대각선 종류 
    for i in range(size): #테이블 크기만큼 탐색을 시도한다.
        L, R = i+len(table), i-len(table) #탐색할 지점에서의 대각선 정보 두가지를 뽑는다.
        if not((L in left) or (R in right) or (i in table)):#대각선 정보가 위에서 구한 종류에 위치한다면 퀸이 겹치므로 안된다.
            target.append(i) #위 조건이 충족된다면 배치할 수 있으므로 경우의 수에 추가한다.
    return target

def check(table,size):
    global answer
    if len(table) == size: #테이블이 사이즈만큼 만들어졌다 -> 퀸이 필요한 만큼 배치되었다.
        answer += 1 #전부 배치한 경우이니 answer를 1 추가한다.
    else: #테이블이 완전히 만들어지지 않았다.
        target = diag(table,size) # 다음 열에 배치시킬 수 있는 경우의 수를 target에 담는다.
        if len(target) > 0: # 경우의 수가 존재한다면? -> 배치하고 다음 수를 확인한다.
            for i in target: # 경우의 수를 추가하고 확인한 다음 원상복구 시킨다.
                table.append(i) # 퀸을 배치한다.
                check(table,size) # 재귀
                del table[-1] #원상복구

T = int(input())

for test_case in range(1, T+1):
    input_num = int(input())
    answer = 0
    check([],input_num) #시작
    print("#"+str(test_case),answer)

 

아이디어

행, 열의 합과 차이를 이용하면 해결할 수 있다.

합 또는 차가 같은 경우 같은 대각선에 위치한다고 생각할 수 있으며 

배치한 퀸들의 대각선 정보를 저장한 다음 테이블 크기의 range(N) 중에서 겹치지 않는 위치만 찾아보는 식으로

해결할 수 있게 된다.

 

아이디어는 예전문제를 풀면서 이해했는데 착각해서 

right = [-i+table[i] for i in range(len(table))]# 두번째 대각선 종류

에서 처음에 i - table[i]를 했다가 왜 틀렸는지 모르고 20~30분 시간을 버린 듯 하다.