[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1799번 _ 비숍

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

1799번: 비숍

[문제]

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

< 그림 1 >

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

< 그림 2 >

< 그림 3 >

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

 

[입력]

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

[출력]

첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

 

[아이디어]

1) 대각선 방향 별로 2개의 visit을 관리해야 한다.

2) k=0부터 2n-1까지의 iteration에서,

k=0일 때: (0,0)

k=1일 때: (1,0), (0,1)

k=2일 때: (2,0), (1,1), (0,2)

...

k=2n-2일 때 (n-1,n-1)

의 순서로 해당 좌표들에 대해 비숍을 놓을 수 있는지 여부에 따라 비숍을 놓거나 놓지 않는다.

3) 모든 대각선에 위치한 점에 대해 0(비숍을 놓을 수 없음)이거나 다른 비숍과 만나는 경우에도 다음 iteration으로 넘어가야 하므로, check로 해당 여부를 확인하고 아무 자리에도 놓지 못했다면 다음 iteration으로 넘어가도록 한다.

4) 매 함수의 시작마다 현재 cnt의 값이 저장한 최댓값보다 크다면 업데이트 하도록 한다.

# Pypy3 통과
n=int(input())
g = [list(map(int, input().split())) for _ in range(n)]

visit1 = [0]*(2*n-1)
visit2 = [0]*(2*n-1)
queens = [];cnt=0; max_ = 0
def bishop(k):
    global cnt, max_
    check = 0
    max_ = max(max_,cnt)
    if k==2*n-1:
        return
    for j in range(k+1):
        if 0<= k-j <n and 0<= j < n:
            if g[k-j][j]==1:
                a = k-2*j+n-1; b = k
                if not visit1[a] and not visit2[b]:
                    check += 1
                    visit1[a] = 1; visit2[b] = 1
                    cnt += 1
                    bishop(k+1)
                    cnt -= 1
                    visit1[a] = 0; visit2[b] = 0
    if not check:
        bishop(k+1)
bishop(0)
print(max_)

살짝 효율이 떨어지는 면이 있는 것 같다. 조건을 보다 타이트하게 관리하거나, 모든 좌표를 흑백으로 구분해 나누어 탐색하는 방법도 있다고 한다.