문제
$4 \times 4$ 격자판에 물고기가 가득 차있다. 각 물고기는 방향과 번호를 갖는다.
맨 처음에는 상어가 가장 왼쪽 위의 칸으로 들어가 그 칸의 물고기를 잡아먹고, 그 물고기의 방향을 가진다.
그다음으로는 모든 물고기가 번호 순으로 움직이는데, 가려는 곳에 물고기가 있으면 두 물고기의 위치가 바뀌는 식으로 움직인다. 만약 그 방향으로 움직일 수 없다면 가능할 때까지 반시계방향으로 45도 회전한 이후에 움직이려고 시도한다.
물고기가 모두 움직인 다음에는 상어가 움직이는데, 현재 방향으로 원하는 칸 수만큼 움직일 수 있다. 지나치는 칸의 물고기는 잡아먹지 않는다. 잡아먹는 물고기 번호 합의 최대값을 구하는 문제이다.
접근
여느 문제와 다름없이 이동 규칙을 잘 구현하기만 하면 어렵지 않게 풀 수 있다. 기본적으로 전체 격자판의 상태를 저장해 놓고, 또 물고기의 이동은 번호 순서대로 일어나므로 각 번호에 해당하는 물고기 위치를 리스트에 저장해 놓아 사용한다. 리스트를 돌면서 물고기를 이동시키는데, 두 물고기 위치를 교환하는 식으로 움직일 때에는 두 리스트를 모두 갱신시켜주면 된다. 현재 방향으로 움직일 수 없을 때에는 방향을 돌려야 하는데, nd=(d+1)%8과 같이 계속 돌 수 있도록 해주면 편리하다.
상어의 움직임은 최대 3개의 선택지가 있으므로, DFS와 백트래킹을 이용해서 정답을 찾아준다. 백트래킹 할때 먹힌 물고기는 되돌리기 어렵지 않은데, 움직인 물고기는 되돌리기 다소 곤란하다. DFS함수 처음에 리스트를 모두 deepcopy해주어서 해결한다. 1초 시간제한이 있지만 문제 크기가 작아 여유롭게 통과할 수 있다.
주의할 점
원 문제 설명에는 물고기가 움직일 수 없으면 움직이지 않는다고 되어있다. 그러나 잘 생각해보면 물고기는 항상 최소한 3칸과 인접해 있으므로 상어가 그 중 한 칸을 차지해도 움직일 곳이 있다. 즉 물고기가 움직일 수 없는 상황은 없다.
테케가 4개나 있기는 하지만, 손으로 직접 풀어보기에 복잡해서 디버깅이 쉽지 않다. 마지막에 디버깅하려고 하지 말고 각 부분을 구현한 다음 예상한 대로 움직이는지 틈틈이 확인해보자.
Code
링크# https://www.acmicpc.net/problem/19236
# Implementation
from sys import stdin
from copy import deepcopy
direction = [[-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]
board = []
for i in range(4):
line = list(map(lambda x: int(x) - 1, stdin.readline().split()))
board.append([[line[0], line[1]], [line[2], line[3]], [line[4], line[5]], [line[6], line[7]]])
fish = [[] for _ in range(16)]
for row in range(4):
for col in range(4):
pos, d = board[row][col]
fish[pos] = [row, col, d]
def dfs(shark_x, shark_y, shark_d, acc):
# first move fish
global fish, board
save_fish = deepcopy(fish)
save_board = deepcopy(board)
for i in range(16):
r, c, d = fish[i]
if r == -1: # already eaten.
continue
nr = r + direction[d][0]
nc = c + direction[d][1]
nd = d
# maybe fish can always move??
while not (0 <= nr < 4 and 0 <= nc < 4 and (nr, nc) != (shark_x, shark_y)):
nd = (nd + 1) % 8
nr = r + direction[nd][0]
nc = c + direction[nd][1]
# swap position
target_num, target_d = board[nr][nc]
fish[i] = [nr, nc, nd]
if target_num != -1:
fish[target_num] = r, c, target_d
board[nr][nc] = [i, nd]
board[r][c] = [target_num, target_d]
# then, move shark.
ret = acc
for mult in range(1, 4):
nx = shark_x + mult * direction[shark_d][0]
ny = shark_y + mult * direction[shark_d][1]
if not (0 <= nx < 4 and 0 <= ny < 4):
break
target_num, target_d = board[nx][ny]
if target_num == -1:
continue
fish[target_num] = [-1, -1, -1]
board[nx][ny] = [-1, -1]
ret = max(ret, dfs(nx, ny, target_d, acc + target_num + 1))
board[nx][ny] = [target_num, target_d]
fish[target_num] = [nx, ny, target_d]
fish = save_fish
board = save_board
return ret
num, d = board[0][0]
fish[num] = [-1, -1, -1]
board[0][0] = [-1, -1]
print(dfs(0, 0, d, num + 1))
