[BOJ] 19237 - 어른 상어 (Python)

 

 

아이디어

 

조건에 따라 상어를 이동하고 상어가 한 마리만 남는 데 걸리는 시간을 출력한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def solution():
    N, M, k = map(int, input().split())
    board = []
    sharks = [[] for _ in range(M+1)]
    for r in range(N):
        board.append([])
        temp = tuple(map(int, input().split()))
        for c in range(N):
            board[-1].append([temp[c], temp[c], 0])
            if temp[c]:
                sharks[temp[c]] = [r, c, 0]
    temp = tuple(map(int, input().split()))
    for i in range(M):
        sharks[i+1][2] = temp[i]-1
    priority = [()]
    for _ in range(M):
        priority.append([tuple(map(lambda x: int(x)-1, input().split())) for i in range(4)])
    cnt = M
    for t in range(1, 1001):
        pos = []
        for i in range(1, M+1):
            if sharks[i]:
                r, c, d = sharks[i]
                temp = []
                if board[r][c][0] == i:
                    board[r][c][0] = 0
                for _d in priority[i][d]:
                    dr, dc = delta[_d]
                    nr, nc = r+dr, c+dc
                    if N > nr >= 0 and N > nc >= 0:
                        if board[nr][nc][1] == 0 or board[nr][nc][2] < t-k:
                            if board[nr][nc][0] == 0 or board[nr][nc][0] > i:
                                board[nr][nc][0] = -1
                                pos.append((nr, nc, i))
                                sharks[i] = [nr, nc, _d]
                            else:
                                sharks[i].clear()
                                cnt -= 1
                            break
                        elif not temp and board[nr][nc][1] == i:
                            temp = [nr, nc, _d]
                else:
                    nr, nc, _d = temp
                    if board[nr][nc][0] == 0 or board[nr][nc][0] > i:
                        board[nr][nc][0] = -1
                        pos.append((nr, nc, i))
                        sharks[i] = [nr, nc, _d]
                    else:
                        sharks[i].clear()
                        cnt -= 1
        for nr, nc, i in pos:
            if board[nr][nc][0] == -1:
                board[nr][nc] = [i, i, t]
        if cnt == 1:
            print(t)
            return
    print(-1)

solution()