본문 바로가기

카테고리 없음

[백준 1799번] 비숍 (Python3)

아주 까다로운 문제였다.

처음에는 모든 좌표를 돌면서 비숍을 놓고, 놓은 위치의 대각선 부분을 체크하는 식으로 브루트 포스 알고리즘으로 풀려고 했다.

코드는 다음과 같다. 

import sys
input = sys.stdin.readline

N = int(input())
board = []
for i in range(N):
  board.append(list(map(int,input().split())))

empty = 0
for i in board:
  empty += sum(i)

def check(y,x):
  cant = set()
  sum,dif = y+x,y-x
  for i in range(N):
    if N>-i+sum>=0:
      if board[-i+sum][i] == 1:
        cant.add((-i+sum,i))
    if N>i+dif>=0:
      if board[i+dif][i] == 1:
        cant.add((i+dif,i))
  return cant

result = 0
def bishop(y,x,cnt):
  global result,empty
  if result == N*2-2:
    return
  if cnt+empty <= result:
    return
  if x==N:
    bishop(y+1,0,cnt)
    return
  if y==N:
    result = max(cnt,result)
    return
  if board[y][x] != 1:
    bishop(y,x+1,cnt)
    return
  cant = check(y,x)
  for y1,x1 in cant:
    board[y1][x1] = 2
    empty -= 1
  bishop(y,x+1,cnt+1)
  for y1,x1 in cant:
    board[y1][x1] = 1
    empty += 1
  bishop(y,x+1,cnt)

bishop(0,0,0)
print(result)

 

그러나 시간초과가 발생하였다. 이후에도 여러번 수정을 거쳤는데도 도저히 시간초과를 해결할 방법을 찾지 못했었다.

그래서 질문게시판을 살짝 봤다가 아주 큰 힌트를 얻었는데, 바로 검은색 칸과 흰색 칸을 분리해서 생각하라는 것이다.

 

취미로 종종 체스를 두는데 왜 이 생각을 못했지 했다. 체스에서 비숍은 검은색칸 비숍은 흰색칸으로 절대 갈 수 없고 그 반대도 마찬가지인 특성이 있다. 이를 활용하면 매우 빠르게 문제를 해결할 수 있다!

 

이 특성을 활용해서 짠 코드는 다음과 같다.

 

 

import sys
input = sys.stdin.readline

N = int(input())

board = []
for i in range(N):
  board.append(list(map(int,input().split())))

blackcheck = {i:0 for i in range(-N//2,N//2+1)}
def black(n,cnt):
  global blackcnt
  if n == N:
    blackcnt = max(blackcnt,cnt)
    return

  cant = True
  for i in range(-N//2,N//2+1):
    if N>n+i>=0 and N>n-i>=0:
      if blackcheck[i]:
        continue
      if board[n+i][n-i]==1:
        cant = False
        blackcheck[i] = 1
        black(n+1,cnt+1)
        blackcheck[i] = 0
  if cant:
    black(n+1,cnt)

whitecheck = {i:0 for i in range(-N//2,N//2)}
def white(n,cnt):
  global whitecnt
  if n == N-1:
    whitecnt = max(whitecnt,cnt)
    return

  cant = True
  for i in range(-N//2,N//2):
    if N>n+i+1>=0 and N>n-i>=0:
      if whitecheck[i]:
        continue
      if board[n+i+1][n-i]==1:
        cant = False
        whitecheck[i] = 1
        white(n+1,cnt+1)
        whitecheck[i] = 0
  if cant:
    white(n+1,cnt)

blackcnt = whitecnt = 0
black(0,0)
white(0,0)
print(blackcnt+whitecnt)

알고리즘을 요약하면

1. 칸을 흑색, 백색일때로 나눈다.

2. 흑색인 경우 (n,n), 백색일 경우 (n+1,n)을 기준으로 (제일 가운데 대각선그래프라고 생각하면 된다) 칸을 구분한다.

3. 기준칸에 대해서 좌,우 대각선 방향으로 번호를 부여하고 해당 번호에 비숍을 놓으면 그 위치에는 비숍을 놓을 수 없는 식으로 브루트 포스를 진행한다.

 

쉽게 말하면 비숍을 비숍이라고 생각하는게 아니고, 룩처럼 생각하고 문제를 풀면 된다. 흑색칸, 백색칸으로 구분하고 보드를 45도 회전한다고 상상해보자. 그럼 비숍이 대각선이 아닌 가로, 세로로 움직인다고 볼 수 있다. 이렇게 되면 사실상 N-Queen 문제보다 더 쉬워지는 것이다! (N-Queen과는 달리 대각선을 고려하지 않으므로)

 

해당 방법으로 문제를 풀자 무려  56ms만에 통과가 되었다. 다른 사람들 풀이를 보니 내 풀이가 파이썬 중에서 엄청나게 빠른 편인것 같았다.

 

 

오늘의 교훈) 때론 겹치지 않는 경우를 따로 푸는것도 필요하다