문제
https://www.acmicpc.net/problem/19236
코드
'''
move는 물고기가 이동하는 함수
dfs로 상어가 갈 수 있는 모든 경우의 수를 탐색
'''
from pprint import pprint
from copy import deepcopy
d = [[-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]
def move(board, dit):
for i in dit:
y, x = dit[i]
if y == -1 and x == -1:
continue
cnt = 0
dy, dx = d[board[y][x][1]-1]
ny = y+dy
nx = x+dx
while cnt < 8 and (ny < 0 or ny >= 4 or nx < 0 or nx >= 4 or board[ny][nx][0] == -1):
cnt += 1
dy, dx = d[(board[y][x][1]-1+cnt) % 8]
ny = y+dy
nx = x+dx
board[y][x][1] += cnt
board[y][x][1] %= 8
if cnt == 8:
continue
if board[ny][nx][0] == 0:
dit[board[y][x][0]] = [ny, nx]
board[ny][nx] = board[y][x][::]
board[y][x] = [0, 0]
else:
board[ny][nx], board[y][x] = board[y][x], board[ny][nx]
dit[board[y][x][0]], dit[board[ny][nx][0]
] = dit[board[ny][nx][0]], dit[board[y][x][0]]
board = [[] for _ in range(4)]
dit = {}
for i in range(4):
temp = list(map(int, input().split()))
for j in range(0, 8, 2):
board[i].append([temp[j], temp[j+1]])
dit[temp[j]] = [i, j//2]
dit = dict(sorted(dit.items()))
dit[board[0][0][0]] = [-1, -1]
sum_v = board[0][0][0]
board[0][0][0] = -1
answer = 0
def dfs(y, x, sum_v, board, dit):
global answer
answer = max(answer, sum_v)
temp = deepcopy(board)
tempdit = deepcopy(dit)
move(temp, tempdit)
dy, dx = d[temp[y][x][1]-1]
ny = y
nx = x
for i in range(4):
ny += dy
nx += dx
if 0 <= ny < 4 and 0 <= nx < 4 and temp[ny][nx][0] > 0:
value = temp[ny][nx][0]
direction = temp[y][x][1]
posy, posx = tempdit[value]
temp[y][x] = [0, 0]
temp[ny][nx][0] = -1
tempdit[value] = [-1, -1]
dfs(ny, nx, sum_v+value, temp, tempdit)
temp[y][x] = [-1, direction]
temp[ny][nx][0] = value
tempdit[value] = [posy, posx]
dfs(0, 0, sum_v, board, dit)
print(answer)풀이
복잡한 시뮬레이션 구현 문제라서 사실 로직이 없습니다
move 함수는 상어가 이동 후 물고기들이 움직이는 시뮬레이션 함수이고 dfs로 재귀를 돌면서 상어가 갈 수 있는 곳들을 모두 탐색하면서 최고 값을 갱신했습니다![]
