개발 학습 블로그입니다.

3 minute read

백준 문제 중 9663번

https://www.acmicpc.net/problem/9663

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오

입력

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

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

풀이

Try1

가능여부 판단을 함수로 구현

이 문제는 꽤나 유명한 문제라 익숙했지만, 아무 배경도 없이 풀어야 한다면 상당히 어려웠을듯 하다.

1차적으로 그냥 단순하게 브르투포스로 해결이 가능하지만 시간제한에 걸리게된다.

그래서 불가능이 판단되는 순간 스킵을 하는 백트래킹이 필요하다.

대표적인 백트래킹 문제로 퀸이 서로 공격하지 못하려면 아래의 두 조건을 만족해야한다.

  1. 같은 행이나 열에 다른 퀸이 있어서는 안된다.
  2. 같은 대각선상에 다른 퀸이 있으면 안된다.

코드의 흐름은 이렇다. 한 열이나 행을 기준으로 잡고(열을 기준으로 설명하겠다.)

n개의 열에 반복문으로 0번째 열부터 n-1번째 열까지 순차적으로 퀸을 배치한다고 생각해보자.

먼저 각 인덱스는 열의 번호, 각 인덱스의 값은 해당열에 배치된 퀸의 행의 번호를 나타내는 n크기의 리스트를 row를 선언하고 None으로 초기화 한다.

x 번째 열에 퀸을 두는 함수 dfs(x)를 선언한다.

dfs(x)함수 내부에서는 row[x]에 어떤 행에 퀸을 두는게 적절한지 판단하기 위해서 for 문을 통해 0번째 행부터 n-1행까지 퀸을 배치하고 해당 배치가 가능한지 판단하는 is_possible(x) 함수를 통해 검증한다.

  • is_possible(x)함수 내부에서는 현재까지의 row[0] ~ row[x-1]들과 해당 함수를 호출하기전 배치된 row[x]와의 관계 즉 처음 말한 두조건에 해당된다면 배치가 불가능한 row[x]의 값(행)이므로 False를 반환하고 모든 조건에 해당이 되지 않는다면 True를 반환한다.

is_possible(x)를 빠져나오고 True를 반환한다면 다음 열의 배치 즉 dfs(x+1)을 재귀적으로 호출하고 False를 반환한다면(백트래킹) row[x]에 다음 행을 넣어보는 반복문으로 돌아가게된다.

dfs를 재귀적으로 호출하다가 열의 번호 x가 n이 된다면 n-1번 열까지 배치를 마쳤음을 의미하고 그러므로 return을 통해 종료한다.

dfs로 모든 경우를 백트래킹하며 판단했음으로 조건을 만족하는 경우만 남게된다.

그리고 다음은 두조건을 판단하는 방법을 구현하는 과정이다.

  1. 같은 행이나 열에 다른 퀸이 있어서는 안된다.

row[x]=y 를 x열에 y를 배치한다로 가정하면서 1번의 조건은 단순히 row[0] ~ row[x-1]까지의 값들 모두가 row[x]와 다르다면 만족하게 된다.

  1. 같은 대각선상에 다른 퀸이 있으면 안된다.

이 부분이 이 문제의 가장 까다로운 부분이 아닐까 싶다. 먼저 위에서 부터 열을 하나씩 차례대로 채워나가며 검증을 하는 방법이기 때문에 현재 처리하고 있는열 [x] 아래로 존재하는 대각선을 고려하지 않아도 된다.

그러고나면 row[x]에 배치된 퀸 y의 좌표를 (x,y)라 할때 abs(x-y)의 함수의 그래프가 (x,y)를 기준으로 v모양으로 꺾인 그래프를 나타냄을 알 수 있다.

즉 row[0] ~ row[x-1]까지의 퀸들이 존재하는 행들에 대해 abs(row[x] - row[i]) == abs(x-i)를 만족한다면 대각선으로 겹침을 판단 할 수 있다.

이를 코드를 나타내면 다음과 같다.

n = int(input())

 # 각열에 배치할 퀸 리스트 선언
row = [None]*n

ans = 0

def is_possible(x):

    for i in range(x):
        if row[x]==row[i] or abs(row[x]-row[i])==(x-i):
            return False
    return True

def dfs(x):

    global ans

     # n-1번 열까지 배치완료
    if x == n:
        ans+=1
        return

     # row[x]에 하나씩 배치해보면 판단
    for i in range(n):
        row[x]=i

         # 배치된 row[x]와 이전 row들이 조건을 만족한다면
         # 다음 열 배치(dfs(x+1))를 재귀적으로 호출
        if is_possible(x):
            dfs(x+1)



dfs(0)
print(ans)

4
2

Try2

가능 여부 판단을 인덱스 접근을 통해 구현

그러나 위의 코드는 시간초과가 뜬다.

그래서 is_possible을 연산을 통해 외부 함수로 호출하는게 아닌 dfs내부에서 대각선에 해당하는 배열의 인덱스에 접근해 True False를 판단할 수 있게 코드를 개선했다.

일단 코드부터 살펴보는게 더 이해가 빠를것 같다.

n = int(input())

row = [None]*n
results = []

 # 체스판 배치상황을 관리할 배열 선언
flag_a = [False]*n
flag_b = [False]*(2*n)
flag_c = [False]*(2*n)

ans = 0

def dfs(x):
    
    if x == n:
        results.append(row[:])
        return
    for i in range(n):
    
         # is_possible을 flag로 개선
        if flag_a[i] or flag_b[x+i] or flag_c[x-i+n-1]:
            continue
        row[x] = i
        flag_a[i], flag_b[x+i], flag_c[x-i+n-1] = True, True, True
        dfs(x+1)
        flag_a[i], flag_b[x+i], flag_c[x-i+n-1] = False, False, False


dfs(0)
print(results)
print(len(results))

4
[[1, 3, 0, 2], [2, 0, 3, 1]]
2

처음 코드와 흐름은 같으나 조금더 직관적이고 빠른 방법이다.

같은 행에 있는 퀸의 판단은 flag_a에서 관리하고 이는 직관적으로 바로 알 수있다. 그러나 문제는 각각의 대각선에 해당하는 flag_b와 flag_c이다. 체스판에서 대각선을 긋는다고 생각하자.

flag_b는 오른쪽위에서 왼쪽아래로 향하는 대각선들에 인덱스를 매긴것이고, 왼쪽 위부터 순서대로 0,1, … (2n)-1 까지 2n개 존재하게 된다.

flag_c는 왼쪽위에서 오른쪽아래로 향하는 대각선들에 인덱스를 매긴것이고, 왼쪽 아래부터 순서대로 0,1, … (2n)-1 까지 2n개 존재하게 된다.

인덱스를 위와 같이 생각하기 위해서는 약간의 조작이 필요하다. flag_b는 x+i로 flag_c는 x+i+n-1로 접근할 수 있다.

이제 dfs를 재귀적으로 호출하며 row[x]에 i를 배치할때 flag들도 최신화를 해주고 다음 열 배치인 dfs(x+1)을 호출하고 호출이 끝난다면 flage들을 다시 False로 최신화 해주는 단계를 추가하면된다.

모든 단계를 dfs로 재귀적으로 호출하되 flag들이 하나라도 True가 되면 스킵하는 백트래킹이 완성었다. 이를 코드로 구형하면 다음과 같다.

Leave a comment

You may also enjoy