백준 #1799 - [G1] 비숍 : 백트래킹, N-Queen, 재귀 분리

(python3)

1799번: 비숍

 

 

N-queen 의 추억

n퀸.. 유명한 알고리즘 문제죠 처음 이 문제를 마주쳤을 때 혼자서 풀어보겠다고 이틀을 머리 싸맸던 기억이 나네요..ㅋㅋㅋ 이후 다른 알고리즘 책을 읽으면서 명료한 풀이법을 알게 됐었습니다.

 

n-queen 의 기본 아이디어는 "우상향으로 같은 대각선의 경우 x+y 가 동일하다는것, 우하향으로 같은 대각선의 경우 x-y 가 동일하다는것" 입니다. 우상향, 우하향 대각선을 의미하는 배열을 각각 놓고 그 대각선에 이미 기물이 있다면 flag 를 1 로, 없다면 0 으로 설정하는 방식을 사용합니다. 이 방식을 취하면 (N*2-1) 칸짜리 배열 두개로 체스판 전체 정보를 가져가지 않고도 기물을 놓을 수 있는지 여부를 판단할 수 있습니다. 물론 체크하는 속도도 훨씬 빨라집니다.

 

 

서로 영향을 주지 않는 칸들 끼리는 재귀를 분리하자

일단 이 문제는 새로운 비숍을 놓을 수 있는지 여부를 엔퀸 방식으로 처리해줄 필요가 있습니다.

 

그리고 추가로, 체스판의 흰칸과 검은칸을 따로 분리해서 재귀 탐색을 해주어야합니다.

 

문제 조건의 맥시멈인 10x10 체스판을 생각해보겠습니다.

모든 경우의 수를 한번에 탐색하려면 $2^{100}$ 의 연산을 돌아야합니다. 그런데 비숍의 경우 대각선상에서만 서로 영향을 주고 받기 때문에 검은칸은 흰칸에 영향을 주지 못합니다. 그 반대도 마찬가지구요. 서로 영향을 주고받는 칸들끼리만 재귀를 돌리는게 훨씬 효율적입니다.

 

흰칸 위에 올라갈 수 있는 비숍의 최대 개수와 검은칸 위에 올라갈 수 있는 비숍의 최대 개수를 따로 구해서 더해주게 되면, 각각 50칸씩 확인하면 되기 때문에 $2^{50} + 2^{50}$ 으로 해결이 가능합니다.

 

 

시간복잡도

여러 블로그들에 $O(2^{N/2*N/2})$ 라고 적혀있었는데, 가로 세로가 각각 절반으로 주는게 아니라, 탐색하는 칸을 절반씩 쪼개는 것이라 제 생각엔 $O(2^{N*N/2})$ 가 맞는 것 같습니다. 

 

일반적으로 백준 1초에 1억 연산이라 2^N 의 경우 1초에 N=20 까지 제한이라고 하는데.. 잘 모르겠습니다. 로컬에서 10x10 체스 보드로 time 을 측정하면 0.7초 가 찍히더라구요.

 

코드

import sys
import time
def solution(input) : 
	# 입력받기
    N = int(input().strip())
    MAP = []
    for _ in range(N) :
        MAP.append(list(map(int,input().split())))
    
    # N-Queen 스타일로 새로운 비숍을 놓을 수 있는지 체크하기 위한 배열
    RD = [0] * 20 # r+c (우상향 대각선)
    LD = [0] * 20 # r-c+N (우하향 대각선)
    global maxcnt
    maxcnt = 0
    def bt(r,c,cnt,wb) : # wb=0 : (0,0) 부터 시작하는 케이스 (검정) / wb=1 : (1,0) 부터 시작하는 케이스 (흰색)
        global maxcnt
        if r>=N : # 행을 끝까지 돈 경우
            maxcnt = max(maxcnt,cnt)
            return
        if c+2 >= N : # 열의 끝에 도달했으면 다음 행으로 이동, 다음행 시작 컬럼은 wb로 맞춘다
            nr=r+1
            nc=(nr+wb)%2
        else :
            nr=r
            nc=c+2
        
        bt(nr,nc,cnt,wb) # 새 비숍을 안놓고 진행

        if MAP[r][c] : # (r,c) 가 초기 맵 상 놓을 수 있는 곳 일때
            if RD[r+c] or LD[r-c+N] : # 다른 비숍의 영향으로 놓을 수 없다면 끝
                return
            else : # 놓을 수 있다면 놓고 진행
                RD[r+c] = 1
                LD[r-c+N] = 1
                bt(nr,nc,cnt+1,wb)
                RD[r+c] = 0 # 빠져나올땐 다시 빈칸으로 바꿔놓기
                LD[r-c+N] = 0
    
    F = 0
    bt(0,0,0,0) # 검정색 체크
    F+=maxcnt
    maxcnt = 0
    bt(0,1,0,1) # 흰색 체크
    F+=maxcnt
    print(F)

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac