[SWEA 2806번] 파이썬 - N-Queen

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

SW Expert Academy

 

 

# 조건

• 8*8의 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제
• 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다.
• 조금 더 일반화시켜 N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수를 구하시오.

 

 

# 접근 방법 및 Solution

• "모든 경우의 수"인 브루트 포스로 해결할 수 있지만
• 이후의 사건이 이전의 사건에 종속적이므로 조건문 통해 가지치기 가능
• 따라서, 재귀 함수를 통해 백트래킹으로 풀어주었다.
• 2차원 배열을 사용해주지 않고 인덱스 = 행, 값 = 열로 사용해주었다.
• 따라서, row[x] = row[i]인 경우 같은 열이므로 불가능, abs[row[x] - row[i]] = x-i 인 경우 (열과 열의 차이) = 행의 차이는 대각선의 규칙이므로 불가능 조건으로 걸어주었다.

• row = [1,3, 0, 2]의 예시 -> 0행의 1열, 1행의 3열에 퀸이 존재
• 아래는 백트래킹 구현 의사코드

첫 줄부터 퀸을 놓은 후 2번째 줄 체크	-> 된다면 3번쨰줄 내려간다.
					-> 안된다면 다시 2번째 체크 - 또 안된다면 1번 줄 다시체크

 

def adjacent(x):  # x와 i 가 같으면 행이 같은거 근데 for문을 보면 x와 i가 같을 수가 없다.
    for i in range(x):  # 인덱스가 행  row[n]값이 열
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:  # 열이 같거나 대각선이 같으면 false
            return False  # 대각선이 같은경우는 두 좌표에서 행 - 행 = 열 - 열 이 같으면 두개는 같은 대각선상에 있다.
    return True


# 한줄씩 재귀하며 dfs 실행

def dfs(x):
    global result

    if x == N:
        result += 1
    else:
        # 각 행에 퀸 놓기
        for i in range(N):  # i 는 열번호 0부터 N 전까지 옮겨가면서 유망한곳 찾기
            row[x] = i
            if adjacent(x):  # 행,열,대각선 체크함수 true이면 백트래킹 안하고 계속 진행
                dfs(x + 1)

T = int(input())
for tc in range(1, T+1):
 
    N = int(input())
    row = [0] * N
    result = 0
  
    dfs(0)

    print(f'#{tc} {result}')

 

 

• 실패 코드를 리뷰하며 배운 점
  • 재귀 함수에서 리스트를 상속하는 경우
    1. 그냥 건네 주면 - 얕은 복사로 인해 상위 그래프가 같이 참조된다.
    2. 따라서, a = b [:] 또는 deepcopy 함수를 이용해 딥 카피를 해주어야 독립적인 탐색이 가능

 

[참고] https://sso-feeling.tistory.com/415