이번 문제는 삼성 기출 문제로, 시뮬레이션과 구현에 포함된 문제이다. 처음에는 상어가 움직일 수 있는 모든 방향을 저장하고, 이 방향 리스트를 가지고 상어를 이동시켰다. 물고기는 리스트를 만들어 좌표에 있는 물고기의 이동 방향을 담아두었다. 그리고 이 리스트를 순회하며 물고기의 이동을 구현하였다. 초기에 물고기들의 위치를 담은 리스트를 복사해두고, 이 과정을 모두 마친 후에 기존 리스트에 값들을 합치도록 하였다. 테스트케이스의 결과값이 큰 경우에 대한 결과만 다르게 나와 오답처리를 받았다. 코드가 너무 복잡하게 작성되기도 하였고, 풀이 시간도 꽤 걸리는 바람에 정확하게 틀린 부분을 찾기가 너무 어려웠다.

코드를 새로 짜기로 하고 다시 코드를 구현해보았다. 전에는 백트레킹으로 상어의 이동 방향을 리스트로 만들었다면, 이번에는 백트레킹으로 상어의 이동방향을 만들어 바로바로 상어를 이동시키는 것이었다. 최종적인 이동 방법을 결정하기 위해 이동 과정에서 잡히는 물고기의 수를 저장하는 인자를 만들었고, 상어가 왔던 위치에 다시 가는 경우를 아예 배제시켰다. 백트레킹으로 구현하면 상어의 이동이 사전순으로 진행되기 때문에 그 부분은 따로 고려하지 않아도 되었다.

물고기의 이동, 복사, 냄새의 사라짐은 전의 코드를 그대로 사용하였다. 이렇게 새로 구현하니 코드도 훨씬 깔끔해졌고, 정답처리를 받을 수 있었다.

Code

import copy

m, s = map(int, input().split())
grid = [[[] for _ in range(4)] for _ in range(4)]
for _ in range(m):
    fy, fx, d = map(int, input().split())
    grid[fy-1][fx-1].append(d-1)
dy, dx = [0, -1, -1, -1, 0, 1, 1, 1], [-1, -1, 0, 1, 1, 1, 0, -1]
sdy, sdx = [-1, 0, 1, 0], [0, -1, 0, 1]
sy, sx = map(int, input().split())
shark = [sy-1, sx-1]
smell = [[0 for _ in range(4)] for _ in range(4)]
shark_move = []
def move_shark(y, x, cur, cnt, move):
    global max_eaten, shark, eaten
    if cur == 3:
        if max_eaten < cnt:
            max_eaten = cnt
            shark = [y, x]
            eaten = move[:]
        return
    for i in range(4):
        ny, nx = y+sdy[i], x+sdx[i]
        if 0 <= ny < 4 and 0 <= nx < 4:
            if (ny, nx) not in set(move):
                move_shark(ny, nx, cur+1, cnt+len(tmp_grid[ny][nx]), move+[(ny, nx)])
            else:
                move_shark(ny, nx, cur+1, cnt, move)
def move_fish():
    global tmp_grid
    result = [[[] for _ in range(4)] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            while tmp_grid[i][j]:
                nd = tmp_grid[i][j].pop()
                for l in range(nd, nd-8, -1):
                    l %= 8
                    ny, nx = i+dy[l], j+dx[l]
                    if (ny, nx) != tuple(shark) and 0 <= ny < 4 and 0 <= nx < 4 and not smell[ny][nx]:
                        result[ny][nx].append(l)
                        break
                else:
                    result[i][j].append(nd)
    tmp_grid = copy.deepcopy(result)
def copy_complete():
    for i in range(4):
        for j in range(4):
            if tmp_grid[i][j]:
                grid[i][j] += tmp_grid[i][j]
def decrease_smell():
    for i in range(4):
        for j in range(4):
            if smell[i][j]:
                smell[i][j] -= 1
for _ in range(s):
    eaten = []
    max_eaten = -1
    tmp_grid = copy.deepcopy(grid)
    move_fish()
    move_shark(shark[0], shark[1], 0, 0, [])
    for y, x in eaten:
        if tmp_grid[y][x]:
            tmp_grid[y][x] = []
            smell[y][x] = 3
    decrease_smell()
    copy_complete()
answer = 0
for i in range(4):
    for j in range(4):
        answer += len(grid[i][j])
print(answer)