문제
문제 해설
물고기를 먹는 모든 경우의 수를 체크하고 가장 번호가 많은 경우를 찾는 문제입니다. 아기 상어보다 제한사항이 더 까다롭고 물고기와 상어의 이동이 각각 다르기 때문에 따로 구현해야하는 것은 물론, 사소한 제한사항 하나하나 꼼꼼히 읽어야 합니다.
물고기의 이동에 관한 제한사항입니다.
- 번호가 작은 녀석부터 이동한다.
- 이동시 각 방향으로 한칸 씩 이동하는데, 맵 밖을 벗어나거나 상어인 경우는 반시계방향으로 45도 회전한다.
- 360도 회전시에도 이동할 수 없는 경우 이동하지 않는다.
- 이동하려는 칸에 물고기가 이미 존재한다면 위치를 서로 바꾼다.
- 1번부터 16번까지 모든 물고기가 이동한다.
상어의 이동에 관한 제한사항입니다.
- 처음 상어는
(0, 0)에 있는 물고기를 먹고 그 녀석의 방향을 가진다.- 방향을 따라서 몇 칸이든 이동이 가능하며, 해당 칸에 있는 물고기만 먹는다.
- 방향을 따라 먹을 수 있는 물고기가 없다면 집으로 돌아간다.
항상 물고기가 먼저 이동하고 그 다음 상어가 이동합니다.
물고기는 살아있다면 항상 정해진 패턴으로 이동하기 때문에 어떤 경우라도 이동하는 것엔 변함이 없습니다.
하지만 상어의 경우 몇 칸이든 이동이 가능하기 때문에 백트래킹을 이용해 모든 경우의 수를 체크해야 합니다. 따라서 deepcopy를 이용해 물고기를 이동시킨뒤의 그래프를 저장하고 재귀 호출 뒤 아직 먹을 수 있는 물고기가 남아있다면 미리 저장했던 그래프를 활용하면 됩니다.
풀이 코드
import sys
import copy
from collections import deque
input = sys.stdin.readline
dx = -1, -1, 0, 1, 1, 1, 0, -1
dy = 0, -1, -1, -1, 0, 1, 1, 1
graph = [[] for _ in range(4)]
for i in range(4):
temp = deque(list(map(int, input().split())))
for j in range(4):
t = []
t.append(temp.popleft())
t.append(temp.popleft() - 1)
graph[i].append(t)
first_blood = graph[0][0][0]
graph[0][0][0] = 50 # 상어 등장
answer = 0
# 상어 좌표,방향
sharkx, sharky, shark_dir = 0, 0, graph[0][0][1]
def fish_move():
# 번호가 작은 순서부터 이동한다.
for num in range(1, 17):
# 살아있는 물고기 이동
x, y, dir = -1, -1, -1
for i in range(4):
for j in range(4):
if graph[i][j][0] == num:
x, y, dir = i, j, graph[i][j][1]
# 해당 번호의 물고기가 없다
if dir == -1:
continue
for i in range(8):
ndir = dir + i if dir + i < 8 else dir + i - 8
nx = x + dx[ndir]
ny = y + dy[ndir]
# 범위 안, 상어가 아니어야 함
if 0 <= nx < 4 and 0 <= ny < 4 and graph[nx][ny][0] != 50:
# 방향을 바꾼 후
graph[x][y][1] = ndir
# 위치를 서로 바꾼다.
graph[nx][ny], graph[x][y] = graph[x][y], graph[nx][ny]
break
def shark_move(sx, sy, sdir, eat):
global answer, graph
# 물고기 이동 후
fish_move()
# 물고기를 원위치 시키기 위함.
redo = copy.deepcopy(graph)
# 먹을 수 있는 물고기를 탐색한다.
# [번호, x, y]
can_eat = []
for i in range(1, 4):
nx = sx + dx[sdir] * i
ny = sy + dy[sdir] * i
if 0 <= nx < 4 and 0 <= ny < 4 and graph[nx][ny][0] > 0:
can_eat.append([graph[nx][ny][0], nx, ny])
# 먹을 수 있는 고기가 없다
if not can_eat:
answer = max(answer, eat)
return
for num, x, y in can_eat:
graph = copy.deepcopy(redo)
# 먹이를 먹고 그 방향을 가진 후 원래 있던 자리를 비운다.
graph[x][y][0] = 50
graph[sx][sy][0] = 0
shark_move(x, y, graph[x][y][1], eat + num)
shark_move(sharkx, sharky, shark_dir, first_blood)
print(answer)