[Python] 백준 1799 비숍

 

 

 

문제

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

 

< 그림 1 >

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

 

< 그림 2 >

 

< 그림 3 >

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

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

 

 

 

 

 

 

난이도

골드 1

 

 

 

 

코드

import sys

def go(k,cnt) :
    global answer
    if k == (2*n-1) :
        answer = max(answer,cnt)
        return
    
    # 가지치기
    if (cnt + 2*n-1-k) <= answer :
        return

    for i,j in right[k] :
        t = i-j+n-1
        if left[t] :
            left[t] = False
            go(k+1,cnt+1)
            left[t] = True

    go(k+1,cnt)

n = int(sys.stdin.readline())
chess = []
for _ in range(n) :
    x = list(map(int,sys.stdin.readline().split()))
    chess.append(x)
answer = 0

right = [[] for _ in range(n*2 - 1)]
left = [True] * (n*2-1) # 둘 수 있는지

# 우 상향 대각에서 갈 수 있는 곳 저장
for i in range(n) :
    for j in range(n) :
        if chess[i][j] == 1 :
            right[i+j].append((i,j))

go(0,0) # k, cnt
print(answer)

 

 

 

 

 

풀이과정

비숍을 겹치지않게 두려면 우상향 대각선, 좌상향 대각선 들 중 말이 2개 이상 있으면 안된다는 점을 이용해 풀었다.

우선 right 리스트에 우상향 대각선에서 말을 놓을 수 있는 좌표들을 저장해두고,

left에는 좌상향 대각선에 말을 놓을 수 있는지 여부를 나타내었다.

재귀함수를 거치면서 현재 우상향 대각선의 자리들 중 말을 놓을 수 있으면 놓고, 다음 대각선으로 보낸다.

현재 대각선에서 말을 놓지 않고 다음 대각선을 탐색하는 경우도 호출한다.

 

여기까지 구현했을 때는 정답이지만 시간초과가 떴다.

그래서 if문을 이용하여 현재부터 모든 대각선에 말을 놓는다고 해도 최댓값이 될 수 없으면 재귀함수를 return 하도록 가지치기 하였더니 성공하였다!