백준 1799번: 비숍 (Python)

문제

 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

 

< 그림 1 >

 그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

 

< 그림 2 >

 

< 그림 3 >

 정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

해설

N-queen과 유사한 백트래킹 활용 문제이다. 얼핏 보기에는 시간제한이 10초나 되어 널널하고, 퀸보다 고려해야 할 경우가 적어서 더 쉬울 것 같지만.. 문제 난이도가 골드 1인 이유가 있다.

 

처음 시도한 접근 방법은 다음과 같았다.

• 모든 칸에 대해서 비숍을 '놓거나', '놓지 않거나' 2개 경우가 존재한다.
• 따라서 백트래킹을 재귀적으로 구현하여 '놓는 경우', '놓지 않는 경우'를 모두 시뮬레이션한다
• 이후 가장 많은 비숍을 세울 수 있었던 케이스를 정답으로 취한다

아마 이 글을 찾아왔다면 위 방법으로는 해결되지 않는다는 걸 깨닫고 왔을 가능성이 높을 것이다.

왜냐하면 이렇게 모든 경우를 백트래킹으로 돌리게 되면, 최악의 경우 O(2^100) 의 시간복잡도가 생기기 때문이다.

최악의 경우, 1로만 채워진 10x10 체스판

발상의 전환이 필요하다. 바로 '흰색 칸만 있는 보드' 와 '검은 칸만 있는 보드' 두 개로 나누어 각각 백트래킹을 진행한 후 각 결과를 합치는 것이다. 흰 칸의 비숍은 검은 칸을 절대 공격하지 못하고, 검은 칸의 비숍은 흰 칸을 절대 공격하지 못하는 성질을 활용한 것이다.

 

이렇게 하면 검사해야 하는 최대 칸의 개수가 절반으로 줄어들기 때문에, 최악의 경우라도

O(n^25) + O(n^25) 의 시간복잡도를 가질 수 있게 된다.

 

그림을 보며 이해해보자.

 

문제에서 제시한 예제 입력에 따르면, 위 그림처럼 비숍의 놓을 수 있는 위치가 정해진다. 그러나 이 경우, 놓을 수 있는 위치가 모두 13개이므로 O(2^13) 번의 계산이 필요하다.

 

'흰 칸만 있는 보드'와 '검은 칸만 있는 보드' 두 개로 나누어 생각을 해보면, 위 예제는 두 개의 보드로 쪼갤 수 있다.

절대로 비숍은 다른 색깔의 칸에 영향을 미칠 수 없으므로, 각 보드에 배치할 수 있는 비숍의 최대 개수를 서로 더하면 정답이 나온다. 이 경우, O(2^9) + O(2^4) 의 연산만 거치면 되기 때문에 연산횟수가 줄어든다.

 

코드

import copy
from random import randint

results = []


def ExceptColor(arr, color):  # 특정 색을 제외시켜주는 함수
    for i in range(N):
        for j in range(N):
            if color == "white":
                if (i+j) % 2 == 0:
                    arr[i][j] = 0
            if color == "black":
                if (i+j) % 2 != 0:
                    arr[i][j] = 0


def CheckCollision(x, y, bishops):  # (x,y)에 비숍을 놓을 때 충돌 확인
    for bishop in bishops:
        dy, dx = bishop[0], bishop[1]
        if abs(dy-y) == abs(dx-x):
            return True
    return False


def Backtracking(x, y, board, bishops):
    if x == N and y == N-1:  # 체스판 끝에 다다르면
        global results
        results.append(len(bishops))
        return

    if x == N:  # 다음 행 이동
        Backtracking(0, y+1, board, bishops)
        return

    # 비숍을 놓을 수 있으면
    if board[y][x] == 1 and not CheckCollision(x, y, bishops):
        # 비숍을 놓거나
        board[y][x] = 2
        bishops.append((y, x))
        Backtracking(x+1, y, board, bishops)
        board[y][x] = 1
        bishops.pop()
        # 비숍을 놓지 않기
        Backtracking(x+1, y, board, bishops)
    else:
        Backtracking(x+1, y, board, bishops)


N = int(input())
board = [[0]*N for _ in range(N)]
white_board = None
black_board = None
for i in range(N):
    board[i] = list(map(int, input().split()))

white_board = copy.deepcopy(board)
black_board = copy.deepcopy(board)
ExceptColor(white_board, "black")
ExceptColor(black_board, "white")

bishops = []
white_count = 0
black_count = 0

Backtracking(0, 0, white_board, bishops)
white_count = max(results)
results = []
Backtracking(0, 0, black_board, bishops)
black_count = max(results)
print(white_count + black_count)

 

대각선 처리는 이전에 작성한 포스팅을 보면 쉽게 이해할 수 있다.

파이썬 체스판 대각선 경로 구현 팁