[백준 19236번] 청소년 상어 (Python3)

import sys
input = sys.stdin.readline
from copy import deepcopy
dy = [-1,-1,0,1,1,1,0,-1]
dx = [0,-1,-1,-1,0,1,1,1]

def movefish(n,ocean):
  y,x = where[n]
  d = ocean[y][x][1]
  for i in range(8):
    y1,x1 = y+dy[(i+d)%8],x+dx[(i+d)%8]
    if 4>y1>=0 and 4>x1>=0:
      if ocean[y1][x1]:
        if ocean[y1][x1][0] == -1:
          continue
        ocean[y][x] = ocean[y1][x1]
        where[ocean[y][x][0]] = (y,x)
      else:
        ocean[y][x] = 0
      ocean[y1][x1] = (n,(i+d)%8)
      where[n] = (y1,x1)
      break

def moveall(ocean):
  ocean = deepcopy(ocean)
  alive = {i:0 for i in range(1,17)}
  for i in range(4):
    for j in range(4):
      if ocean[i][j]:
        if ocean[i][j][0] != -1:
          alive[ocean[i][j][0]] = 1
        where[ocean[i][j][0]] = (i,j)
  for n in range(1,17):
    if alive[n]:
      movefish(n,ocean)
  return ocean

def DFS(ocean,result):
  global maxresult
  newocean = moveall(ocean)
  sy,sx = where[-1]
  sd = newocean[sy][sx][1]
  newocean[sy][sx] = 0
  sy += dy[sd]
  sx += dx[sd]
  while 4>sy>=0 and 4>sx>=0:    
    if newocean[sy][sx]:
      n,d = newocean[sy][sx]
      newocean[sy][sx] = (-1,d)
      DFS(newocean,result+n)
      newocean[sy][sx] = (n,d)
    sy += dy[sd]
    sx += dx[sd]
  maxresult = max(maxresult,result)

ocean = [[0]*4 for i in range(4)]
for i in range(4):
  data = [*map(int,input().split())]
  for j in range(4):
    ocean[i][j] = (data[j*2],data[j*2+1]-1)

result,d = ocean[0][0]
ocean[0][0] = (-1,d)
where = {}
maxresult = 0
DFS(ocean,result)
print(maxresult)

어마어마한 코드길이의 시뮬레이션 구현문제.

코드짜는데도 오래걸리고, 오타찾는데도 오래걸리고 힘들었다...

 

아이디어 자체는 매우 쉽다.

DFS + 백트래킹을 이용한 브루트포스로 모든 경우의 수를 고려하여 최대값을 구하면 된다.

코드짜는게 오래걸려서 그렇지;

 

그래도 나름 깔끔하게 잘 짠 것 같다. 오타만 아니었어도 ㅋㅋ;

 

 

오늘의 교훈) 오타내지 말자