백준(BOJ) 1799 비숍(Python)

문제 내용

조건

DFS를 두 번 해주면 되는 문제였다.

아이디어는 다음과 같다.

기본적으로 체스판은 흑과 백 격자로 나누어져있다.

비숍은 체스판에서 대각선으로만 움직이는데, 그렇게 되면 흰 칸에 위치한 비숍은 흰 칸으로 밖에 움직일 수 없고, 검은 칸 역시 마찬가지이다.

즉, 흰 칸의 비숍과 검은 칸의 비숍은 서로 영향을 줄 수 없는 것이다.

왼쪽 위 칸에서부터 우상향 대각선의 번호를 매기고, 왼쪽 아래 칸에서부터 우하향 대각선의 번호를 매겨 각 격자의 새로운 고유 넘버를 지정해줬다.

그렇게 하면 대각선 상에 비숍이 하나만 위치해도 그 칸의 고유 넘버와 같은 고유 넘버를 공유하는 칸에는 모두 비숍이 위치할 수 없게 되는 것이다.

예를 들면, (0,1)에 비숍이 위치해있다면 (0,2)와 (2,1)은 각각 첫번째 고유 넘버와 두번째 고유 넘버가 같기 때문에 비숍이 위치할 수 없게 된다.

재귀 함수를 처음 실행할 때 흰 칸만 고려할 것인지, 검은 칸만 고려할 것인지에 대한 타입을 지정해 실행시키는 방식으로 시간복잡도를 줄일 수 있었다.

​

코드는 다음과 같다.

​

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
sys.setrecursionlimit(100000000)

def func(k,a,b,t):
    global x,n
    x=max(x,k)
    nx=(n-1)-a+b
    ny=a+b
    if t:
        for i in range(a,n):
            if i%2==0:
                for j in range(1,n,2):
                    nx=(n-1)-i+j
                    ny=i+j
                    if not visited_x[nx] and not visited_y[ny] and L[i][j]:
                        visited_x[nx]=1
                        visited_y[ny]=1
                        func(k+1,i,j,t)
                        visited_x[nx]=0
                        visited_y[ny]=0
            else:
                for j in range(0,n,2):
                    nx=(n-1)-i+j
                    ny=i+j
                    if not visited_x[nx] and not visited_y[ny] and L[i][j]:
                        visited_x[nx]=1
                        visited_y[ny]=1
                        func(k+1,i,j,t)
                        visited_x[nx]=0
                        visited_y[ny]=0
    else:
        for i in range(a,n):
            if i%2==0:
                for j in range(0,n,2):
                    nx=(n-1)-i+j
                    ny=i+j
                    if not visited_x[nx] and not visited_y[ny] and L[i][j]:
                        visited_x[nx]=1
                        visited_y[ny]=1
                        func(k+1,i,j,t)
                        visited_x[nx]=0
                        visited_y[ny]=0
            else:
                for j in range(1,n,2):
                    nx=(n-1)-i+j
                    ny=i+j
                    if not visited_x[nx] and not visited_y[ny] and L[i][j]:
                        visited_x[nx]=1
                        visited_y[ny]=1
                        func(k+1,i,j,t)
                        visited_x[nx]=0
                        visited_y[ny]=0
    
n=int(input())
x=0
L=[]
for i in range(n):
    L.append(list(map(int,input().split())))
visited_x=[0]*(2*n-1)
visited_y=[0]*(2*n-1)
func(0,0,0,0)
ans=x
x=0
visited_x=[0]*(2*n-1)
visited_y=[0]*(2*n-1)
func(0,0,1,1)
print(ans+x)

코드가 굉장히 길다.

함수 타입이 두 개라 어쩔 수 없지만, 보기에 썩 좋진 않은 것 같다.

처음에는 단순한 백트래킹 문제라고 생각하고 풀었는데, python3으로 실행시키면 시간 초과가, pypy3로 실행시키면 메모리 초과가 계속 터졌다.

어떻게든 시간복잡도랑 공간복잡도를 줄여보겠다고 이것저것 건드려봤는데도 마찬가지라서 결국 처음부터 다시 생각해봤다.

결국 검색을 통해 어떻게 푸나를 찾아봤는데, 사실 보고도 뭔 소린지 잘 몰라서 반 나누는 것만 배웠다. 사실 반 나누는 게 가장 큰 개념이긴 하지만,,

끝까지 혼자 풀지 못 해서 아쉽다.

기억이 휘발될 때 즈음 다시 풀어볼 예정이다.