개구리

우물 안 개구리

백트래킹의 대표적인 예제다. 넴모넴모 문제를 풀고 풀어서 모든 격자를 방문하며 가로방향, 세로방향, 대각선 방향을 체크하는 방식의 풀이를 생각했었다. 상당히 복잡하고 시간도 오래 걸렸다. 많은 시행착오 후에 각각의 행과 열에는 오직 1개의 퀸이 올 수 있다는 것을 생각해낼 수 있었다.

# N - queen
N = int(input())
chess=[-1 for _ in range(N)]
visited=[-1 for _ in range(N)]
ans=0
def queen(x,placed):
    global ans
    
    if placed == N :
        ans+=1
        return 
    
    if x == N :
        return
    
    for i in range(N):
        if visited[i] == -1 : 
            if check(x, i) == True:
                visited[i], chess[x] = 1,i
                queen(x+1,placed+1)
                visited[i], chess[x] = -1, -1
                
    
def check(x, idx):   
    for i in range(N):
        if chess[i] ==-1:
            continue
        if abs(x-i) == abs(idx-chess[i]) :
            return False
    
    return True

queen(0,0)
print(ans)

각 열에 한 개의 queen이 올 수 있다는 점을 이용해 chess 배열과 visited 배열을 만들었다.

구현

  1. chess 배열에는 각 행의 퀸이 몇 번째 열에 위치하는 지 표시한다. 예를 들어 chess[1]=3 일 경우 1번 열 3번 행에 퀸이 위치한 것이다.
  2. visited 배열에는 각 행의 퀸이 사용되었는 지를 표시한다. 굳이 visited 배열을 더 만들 필요 없이 chess 배열만으로도 문제를 풀 수 있지만 쉽게 이해하기 위해 다음과 같이 풀었다.
  3. 백트래킹을 하며 각 행에 퀸을 하나씩 추가한다. 이 때 열을 기준으로 보면 마찬가지로 한 개의 퀸이 올 수 있다. 퀸을 추가하기 전 check 함수를 통해 해당 칸에 퀸을 넣을 수 있는 지 확인한다.
  4. check 함수에서는 abs를 통해 대각선을 확인하고 chess 배열을 확인하여 해당 열에 퀸이 있는 지 확인한다.

N번 행까지 모두 퀸을 놓으면 경우의 수에 1을 추가한다.

댓글남기기

참고