이번 문제는 삼성 기출 문제로, 상어의 이동에 대한 모든 경우를 백트레킹을 통해 구하여 그 중 가장 큰 값을 정답 변수에 저장하는 문제였다. 우선 크게 물고기의 이동과 상어의 이동, 이렇게 2개의 함수로 나눠서 정의하였다.

물고기의 이동의 경우에는 물고기의 방향을 반시계 45도씩 변경해가며 범위 내에 상어의 위치가 아닌 칸을 만나면 그 칸으로 이동을 시켰다. 이동은 fish리스트에서의 지금 물고기와 이동하고자 하는 칸의 물고기의 값을 교환하였고, 물고기의 번호와 방향이 저장되어 있는 grid리스트에서는 현재 물고기의 방향을 변경한 후에 이동하고자 하는 칸과 교환하였다.

상어의 이동은 백트레킹을 통해 구현하였다. 우선 인자로 상어의 y, x좌표와 d방향, 그리고 상어가 지금까지 먹은 물고기의 합 fat, tmp_grid, tmp_fish를 받게 된다. 먼저 여기서 물고기 이동 함수를 호출해주고, 상어의 방향에서 갈 수 있는 모든 칸을 순회하며 상어의 이동 함수를 재귀호출 시켜주었다. 재귀호출을 하기 전에 grid리스트에 tmp_grid를, fish리스트에 tmp_fish를 deepcopy시켜 물고기의 이동 후의 상태를 저장하였고, 상어가 먹을 물고기에 대한 정보를 갱신시켰다. 그리고 재귀호출에 인자로 ny, nx, 상어의 바뀔 방향 tmp[1], 상어가 먹은 물고기의 합, grid, fish를 넣게 된다. 그리고 chk변수를 통해 상어가 이동하였는지의 여부를 확인하는데, 상어가 이동을 하지 못하였다면 answer를 answer과 fat 중의 최댓값으로 갱신해주고 함수를 종료하게 된다.

Code

import copy

grid=[[] for _ in range(4)]
fish=[[] for _ in range(17)]
for i in range(4):
    tmp=list(map(int, input().split()))
    for j in range(4):
        grid[i].append([tmp[2*j], tmp[2*j+1]-1])
for i in range(4):
    for j in range(4):
        fish[grid[i][j][0]]=[i, j]
dy, dx=[-1, -1, 0, 1, 1, 1, 0, -1], [0, -1, -1, -1, 0, 1, 1, 1]
shark=[0, 0, grid[0][0][1]]
fat=grid[0][0][0]
fish[grid[0][0][0]]=None
grid[0][0]=[0, 0]
answer=0
def move_fish(grid, fish):
    for num in range(1, 17):
        if fish[num] is None:
            continue
        y, x=fish[num]
        d=grid[y][x][1]
        for k in range(8):
            nd=(d+k)%8
            ny, nx=y+dy[nd], x+dx[nd]
            if 0<=ny<4 and 0<=nx<4:
                if (ny, nx)==(shark[0], shark[1]):
                    continue
                grid[y][x][1]=nd
                fish[grid[ny][nx][0]], fish[num]=[y, x], [ny, nx]
                grid[y][x], grid[ny][nx]=grid[ny][nx], grid[y][x]
                break
def move_shark(y, x, d, fat, tmp_grid, tmp_fish):
    global answer, shark
    shark=[y, x, d]
    move_fish(tmp_grid, tmp_fish)
    chk=False
    for i in range(1, 4):
        ny, nx=y+dy[d]*i, x+dx[d]*i
        if 0<=ny<4 and 0<=nx<4:
            grid=copy.deepcopy(tmp_grid)
            fish=copy.deepcopy(tmp_fish)
            if grid[ny][nx]!=[0, 0]:
                num=grid[ny][nx][0]
                fish[num]=None
                tmp=grid[ny][nx]
                grid[ny][nx]=[0, 0]
                chk=True
                move_shark(ny, nx, tmp[1], fat+tmp[grid[ny][nx][0]], grid, fish)
    if not chk:
        answer=max(answer, fat)
        return
move_shark(0, 0, shark[2], fat, grid, fish)
print(answer)