이번 문제는 삼성 기출 문제로, BFS를 통해 상어의 이동을 구현하고, 냄새를 저장하는 리스트를 따로 관리하여 해결하였다. 데이터 저장 방식을 확립하는 것이 헷갈리지 않고 해결할 수 있는 방법이라고 생각했고, 이렇게 복잡한 문제는 모듈화하는 것이 풀이에 유리하므로, 각 기능을 함수로 작성하였다. 데이터 저장 방식은 다음과 같이 하였다.

• grid: 2차원 리스트
• d: 1차원 리스트
• priority: 3차원 리스트
• shark: 큐
• smell: 3차원 리스트

함수는 다음과 같이 구성하였다.

• move()
  상어의 이동을 구현
• decrease_smell()
  냄새의 감소를 구현
• check_shark():
  상어가 1마리 남았는지 확인

move()에서는 상어의 이동 우선순위 리스트와 냄새 리스트를 확인하며 상어의 다음 이동 위치를 선정하고 이동시켰다. 이때 상어의 새로운 위치를 새로운 큐에 저장하고, 상어의 새로운 위치가 모두 정해졌다면, 새로운 큐를 순회하며 임시 리스트에 상어의 위치를 갱신해주었다. 이때 만약 이미 그 위치에 상어가 있다면 번호가 더 작은 상어만 남도록 하였고, 이 과정이 모두 끝나면 임시리스트를 순회하며 기존 리스트에 값을 복사하고, 상어의 위치인 경우에는 상어 큐에 값을 넣어주었다.

decrease_smell()에서는 smell리스트를 순회하며 smell리스트가 비어있지 않을 경우에, 두번째 인자가 0이라면 빈 리스트로 갱신해주고, 0이 아니라면 두번째 인자를 1 감소시켜주었다.

check_shark()에서는 shark큐의 길이를 확인하여 1일 경우에만 True를 반환하고, 아닐 경우에는 False를 반환하도록 하였다.

Code

from collections import deque
n, m, k=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
d=list(map(int, input().split()))
for i in range(m):
    d[i]-=1
priority=[[] for _ in range(m)]
for i in range(m):
    for _ in range(4):
        priority[i].append(list(map(int, input().split())))
        for j in range(4):
            priority[i][-1][j]-=1
shark=deque()
smell=[[[] for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if grid[i][j]!=0:
            smell[i][j]=[grid[i][j], k]
            shark.append((grid[i][j], i, j))
dy, dx=[-1, 1, 0, 0], [0, 0, -1, 1]
def move():
    tmp=[[0 for _ in range(n)] for _ in range(n)]
    new_shark=deque()
    while shark:
        num, y, x=shark.popleft()
        chk=False
        for nd in priority[num-1][d[num-1]]:
            ny, nx=y+dy[nd], x+dx[nd]
            if 0<=ny<n and 0<=nx<n:
                if not smell[ny][nx]:
                    new_shark.append((num, ny, nx))
                    d[num-1]=nd
                    chk=True
                    break
        if not chk:
            for nd in priority[num-1][d[num-1]]:
                ny, nx=y+dy[nd], x+dx[nd]
                if 0<=ny<n and 0<=nx<n:
                    if smell[ny][nx] and smell[ny][nx][0]==num:
                        new_shark.append((num, ny, nx))
                        d[num-1]=nd
                        break
    for sn, y, x in new_shark:
        if tmp[y][x]==0:
            tmp[y][x]=sn
        else:
            if tmp[y][x]>sn:
                tmp[y][x]=sn
    for i in range(n):
        for j in range(n):
            grid[i][j]=tmp[i][j]
            if tmp[i][j]!=0:
                shark.append((tmp[i][j], i, j))
                smell[i][j]=[tmp[i][j], k]
def decrease_smell():
    for i in range(n):
        for j in range(n):
            if smell[i][j]:
                if smell[i][j][1]==0:
                    smell[i][j]=[]
                else:
                    smell[i][j][1]-=1
def check_shark():
    if len(shark)==1:
        return True
    return False
answer=0
while not check_shark():
    if answer>=1000:
        answer=-1
        break
    answer+=1
    decrease_smell()
    move()
print(answer)