[PS] BOJ 1799 / 비숍

Minjun Kim

24 Jul 2025 • 9 min read

문제 링크: https://www.acmicpc.net/problem/1799

Thumbnail: Photo by Omar Lopez-Rincon (Unsplash)

N-Queen으로 변환해 풀 수 있는 백트래킹 문제입니다.

풀이

기본적인 풀이는 N-Queen과 동일합니다. 하지만, 비숍을 어떻게 N-Queen 문제의 형태로 변환할지는 충분한 고민이 필요합니다.

아이디어

기본적인 아이디어는 아래 2가지입니다.

체스판을 45도 회전시켜 보면, 비숍 대신 룩을 배치하는 문제로 볼 수 있다.
흑색 칸과 백색 칸의 비숍은 어떤 경우에도 서로 간섭하지 않는다.

1) 45도 회전시켜 룩을 배치하는 문제로 변환하기

N-Queen 문제에서는 퀸을 행 단위로 배치하며, 열이 겹치지 않는지 검사합니다. 하지만 비숍은 수평/수직으로 이동할 수 없고 오로지 대각선으로만 이동이 가능하므로, 퀸과 동일하게 행 단위로 배치할 수 없습니다.

하지만, 체스판을 45도 돌려서 보면 마름모 꼴의 체스판에서 룩을 배치하는 것으로도 볼 수 있습니다. 룩은 수평 및 수직 방향으로만 이동하므로, N-Queen과 동일한 요령으로 접근할 수 있습니다.

회전한 체스판을 기준으로, 행 단위로 룩을 배치해보며, 배치할 때 이전에 말을 배치했던 열인지 검사해주면 됩니다.

체스판을 45도 회전시키게 되면, 기존 체스판과 좌표와 형태가 달라집니다.
예제로 주어진 크기 5의 체스판을 시계방향으로 45도 회전시켜봅시다.

예제 입력

45도 회전한 체스판

기존 체스판의 좌표가 회전한 체스판에서 어떻게 변화하는지 알아봅시다.

입력 받은 기존 체스판의 각 칸의 좌표를 회전된 체스판의 대응되는 각 칸에 (행, 열) 꼴로 표기해 두었습니다. 각 칸의 행, 열 방향의 좌표가 어떻게 변환되는지 그림으로 알아봅시다.

기존 체스판의 좌표를 \((r, c)\)라고 할 때, 회전한 체스판의 행 방향 좌표는 \(r + c\)가 됩니다.

열 방향 좌표는 좀 복잡합니다. 아래 그림에서, 회전한 체스판 배열의 0번 좌표부터 중앙 좌표까지의 거리는 \(N-1\)입니다.

중앙 좌표 \((0, N-1)\)에서 뻗어나가는 두 화살표를 봅시다.

왼쪽 화살표는 기존 체스판을 기준으로 보면, 이 방향은 행 좌표(\(r\))가 증가하는 방향입니다.
동시에, 회전한 체스판에서 열 방향 좌표가 감소하는 방향입니다.

오른쪽 화살표는 기존 체스판을 기준으로 보면, 이 방향은 열 좌표(\(c\))가 증가하는 방향입니다.
동시에, 회전한 체스판에서 열 방향 좌표가 증가하는 방향입니다.

이 세가지 정보를 토대로, 회전한 뒤의 열 방향 좌표는 \(N - 1 - r + c\)임을 알 수 있습니다.

정리하면, \((r, c)\)는 회전한 체스판에서 \((r + c, N - 1 - r + c)\)로 변환됩니다.
이를 이용해, 입력받은 체스판을 회전시켜서 배열에 저장합니다.

# 체스판을 45도 회전시켜서 룩을 배치하는 문제로 바꾼다.
rotated_length = 2 * N - 1
board = [[-1] * rotated_length for _ in range(rotated_length)]  # -1은 실제 체스판에는 존재하지 않는 칸이므로 계산에 사용해선 안된다.
for row in range(N):
    for col, tile in enumerate(map(int, input().split())):
        rotated_r = row + col
        rotated_c = N - 1 - row + col
        board[rotated_r][rotated_c] = tile

N-Queen

이제, 회전한 체스판에서 룩을 배치하는 문제를 풀어봅시다. 이는 N-Queen과 비슷한 방식으로 풀 수 있습니다.

N-Queen은 N개의 행에 퀸을 배치하는 문제로, 각 행마다 각 열에 퀸을 배치해보며 가능한 경우의 수를 찾는 문제입니다. 이때, 퀸끼리 서로 잡지 못하게 배치해야 하므로, 백트래킹에 고려하는 조건은 다음과 같습니다:

이전에 퀸이 배치된 열인가? (퀸은 행/열/대각선 모두 이동하기 때문에)
이전에 배치된 퀸의 대각선에 위치하는가?

회전한 체스판에 룩을 배치한다고 생각하면, 대각선을 고려할 필요가 없기 때문에 이전에 말을 배치한 열인지만 검사해주면 됩니다. 이는 간단한 배열에 배치 여부를 기록하며 백트래킹을 진행해주면 됩니다.

하지만, 이 정도로만 백트래킹을 시도하면 시간 초과를 받게 됩니다. 방문하는 경우의 수를 더 줄여볼 수는 없을까요?

흑/백 비숍을 나눠서 탐색하기

여기서 두 번째 아이디어를 사용합니다.

💡 흑색 칸과 백색 칸의 비숍은 어떤 경우에도 서로 간섭하지 않는다.

비숍은 대각선으로만 이동하므로, 다른 색의 칸에 도달할 수 없습니다. 따라서, 흑색 칸에 있는 비숍과 백색 칸에 있는 비숍을 각각 따로 탐색한 뒤 결과를 합쳐도 무방합니다!

회전한 체스판에서 흑색 칸과 백색 칸은 각각 홀수/짝수 행에 번갈아 나타나므로, 홀수 행끼리 / 짝수 행끼리 나누어 백트래킹을 진행해주면 시간초과없이 답을 구할 수 있습니다.

bishops = [[None for _ in range(rotated_length)] for _ in range(2)] # tuple[int, int]: bishop's position (r, c)
columns = [[True for _ in range(rotated_length)] for _ in range(2)] # 배치 가능한 열이면 True, 그렇지 않다면 False.
    
# 룩은 각 행/열에 한개씩만 존재할 수 있다.
# 최적화 팁: 비숍의 특징을 고려해보면, 흑칸 비숍과 백칸 비숍은 원래 서로 간섭하지 못한다. 따라서, 흑칸과 백칸을 나누어 푼 후 답을 더해도 된다!
max_bishops = [0, 0]
def backtracking(row, count, is_black):

    if row >= rotated_length:
        max_bishops[is_black] = max(max_bishops[is_black], count)
        return

    for j in range(rotated_length):
        if board[row][j] == 1 and columns[is_black][j]:
            columns[is_black][j] = False
            bishops[is_black][count] = (row, j)
            backtracking(row + 2, count + 1, is_black)
            columns[is_black][j] = True
            bishops[is_black][count] = None
    backtracking(row + 2, count, is_black)

# 홀수 행과 짝수 행을 나눠서 DFS
backtracking(0, 0, 0)
backtracking(1, 0, 1)

전체 코드

input = open(0).readline
N = int(input())
# 체스판을 45도 회전시켜서 룩을 배치하는 문제로 바꾼다.
rotated_length = 2 * N - 1
board = [[-1] * rotated_length for _ in range(rotated_length)]  # -1은 실제 체스판에는 존재하지 않는 칸이므로 계산에 사용해선 안된다.
for row in range(N):
    for col, tile in enumerate(map(int, input().split())):
        rotated_r = row + col
        rotated_c = N - 1 - row + col
        board[rotated_r][rotated_c] = tile

bishops = [[None for _ in range(rotated_length)] for _ in range(2)] # tuple[int, int]: bishop's position (r, c)
columns = [[True for _ in range(rotated_length)] for _ in range(2)] # 배치 가능한 열이면 True, 그렇지 않다면 False.
    
# 룩은 각 행/열에 한개씩만 존재할 수 있다.
# 최적화 팁: 비숍의 특징을 고려해보면, 흑칸 비숍과 백칸 비숍은 원래 서로 간섭하지 못한다. 따라서, 흑칸과 백칸을 나누어 푼 후 답을 더해도 된다!
max_bishops = [0, 0]
def backtracking(row, count, is_black):

    if row >= rotated_length:
        max_bishops[is_black] = max(max_bishops[is_black], count)
        return

    for j in range(rotated_length):
        if board[row][j] == 1 and columns[is_black][j]:
            columns[is_black][j] = False
            bishops[is_black][count] = (row, j)
            backtracking(row + 2, count + 1, is_black)
            columns[is_black][j] = True
            bishops[is_black][count] = None
    backtracking(row + 2, count, is_black)

# 홀수 행과 짝수 행을 나눠서 DFS
backtracking(0, 0, 0)
backtracking(1, 0, 1)
print(sum(max_bishops))

solution.py