백준 19237 어른상어

단순 구현 문제로 문제가 요구하는 요구사항을 정확하게 구현만 하며되는 문제다.
같은 공간에 두마리 이상의 상어가 접근하려는 경우 최소힙을 사용해서 O(1)시간에 어떤 상어를 남길지 파악했다.
또한 1부터 우선순위를 갖기 때문에 deque를 사용하여 1이 돌아오는 경우를 한 사이클로 다루는 방식을 사용함.

from collections import deque
import copy
import heapq

dx = [0, -1,1,0,0] # 상(1)하(2)좌(3)우(4)
dy = [0, 0,0,-1,1] # 상(1)하(2)좌(3)우(4)
s_prior = []
shark_info = []

def answer(sharkQ, k, board, smell_info):
    global shark_info, s_prior, dx, dy
    time = 0
    _curB = copy.deepcopy(board) # 이동중을 저장하는 보드
    n = len(board) # 공간의 크기
    while len(sharkQ)>1:
        if time > 1000:
            return 0
        tShark = sharkQ.popleft()
        if tShark == 1: # 한번의 이동이 끝남.
            if len(sharkQ) == 0: # 1번 상어만 남은 경우 종료.
                return time
            time +=1
            if time > 1:
                # 냄새의 값을 1씩 줄여준다.
                for x in range(n):
                    for y in range(n):
                        target = _curB[x][y]
                        #if target[0] != 0:
                        if smell_info[x][y]>0: # 이전에 상어가 남긴 냄새가 있으면 -1
                            smell_info[x][y] -= 1
                            if smell_info[x][y] == 0: # 냄새의 지속성이 끝난 경우 상어 흔적도 삭제
                                _curB[x][y] = [0]
                        else:
                            smell_info[x][y] = k
                        if len(target) >= 2: # 새로 추가된 상어가 있는 경우
                            smell_info[x][y] = k
                            winShark = target[1]
                            nonZero = target[1:]
                            if len(nonZero)>=2:
                                heapq.heapify(nonZero)
                                winShark = nonZero[0]
                                removeIdx= nonZero[1:]
                                for r in removeIdx:
                                    if r not in sharkQ: # 이미 삭제된 상어는 패스
                                        continue
                                    sharkQ.remove(r) # 선택 받지 못한 상어는 제거
                            _curB[x][y] = [winShark]

        # 상어 이동
        sx, sy, sd = shark_info[tShark] # x,y,방향
        prev = []
        regi = False
        for checkDir in s_prior[tShark][sd-1]:
            nx = sx + dx[checkDir]
            ny = sy + dy[checkDir]
            if not (0<=nx<n and 0<=ny<n): # 다음 방향 확인
                continue
            if _curB[nx][ny][0] == 0: # 빈칸인 경우 nx, ny 자리에 후보로 올림
                _curB[nx][ny].append(tShark)
                shark_info[tShark] = [nx,ny, checkDir]
                regi = True
                break
            elif _curB[nx][ny][0] == tShark: # 이전에 방문한 경우
                prev.append([nx,ny, checkDir])
                continue

        if not regi and len(prev) > 0: # 갈곳이 없어서 이전에 방문한 자리에 다시 도착한 경우
            _curB[prev[0][0]][prev[0][1]][0] = tShark
            smell_info[prev[0][0]][prev[0][1]] = 0 # smell은 위에서 초기화하기때문에 0으로..
            sharkQ.append(tShark)
            shark_info[tShark] = prev[0]
            continue
        if regi:
            sharkQ.append(tShark)

    return time
def main():
    global s_prior, shark_info
    # 격자 크기, 상어 개수, 냄새지속시간 입력
    N,M,k = list(map(int, input().split()))
    sharkQ = deque([i for i in range(1,M+1)])
    # 상어의 현재 위치 입력
    board = [[] for _ in range(N)]
    smell_info = [[] for _ in range(N)]
    shark_info = [[] for _ in range(M+1)] # 1
    for i in range(N):
        data = list(map(int, input().split()))
        smell = [0 for _ in range(N)]
        _temp = []
        for j in range(len(data)):
            if data[j] > 0:
                shark_info[data[j]] = [i,j]
                smell[j] =k
            _temp.append([data[j]])
        board[i] = _temp
        smell_info[i] = smell

    # 상어의 현재 방향
    s_cur_dir =  list(map(int, input().split()))
    ii = 1
    for d in s_cur_dir:
        shark_info[ii].append(d)
        ii+=1

    s_prior = [[] for _ in range(M+1)]
    # 상어 회전 우선순위 입력
    for i in range(1,M+1):
        _temp = []
        for _ in range(4): # 상,하,좌,우일때의 방향 우선순위
            temp = list(map(int, input().split()))
            _temp.append(temp)
        s_prior[i] = _temp

    
    #print(moveShark(0, board, sharkQ,k))
    ans = answer(sharkQ, k, board, smell_info)
    print(ans-1)

if __name__ == "__main__":
	main()