280. 어른 상어

백준

1. Python

import sys
from copy import deepcopy
input = sys.stdin.readline
n, m, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
smell = [[[0,-1]]*n for _ in range(n)]
shark_dir = list(map(int,input().split()))
for i in range(m):
    shark_dir[i] = [shark_dir[i]]
    for _ in range(4):
        shark_dir[i].append(list(map(int,input().split())))

dir = [(-1,0),(1,0),(0,-1),(0,1)]
cnt = 0
temp = 0
while True:
    if temp == m - 1 : 
        print(cnt)
        break
    if cnt >= 1000:
        print('-1')
        break

    for i in range(n):
        for j in range(n):
            if board[i][j] != 0:
                smell[i][j] = [k,board[i][j]]

    nboard = deepcopy(board)
    for i in range(n):
        for j in range(n):
            if board[i][j] != 0:
                d, up, down, left, right = shark_dir[board[i][j]-1]
                arr = [up, down, left, right]
                flag = 0
                for p in range(4):
                    dx, dy = dir[arr[d-1][p] - 1]
                    # 인접한 영역에 냄새가 0 인 경우 우선순위를 고려
                    if -1 < i+dx < n and -1 < j+dy < n and smell[i+dx][j+dy] == [0,-1]:
                        # 이동하는 자리에 어떠한 상어도 없을경우
                        if nboard[i+dx][j+dy] == 0:
                            nboard[i+dx][j+dy] = board[i][j]
                            nboard[i][j] = 0
                        else:
                            if nboard[i+dx][j+dy] > board[i][j]:
                                nboard[i+dx][j+dy] = board[i][j]
                            temp += 1
                            nboard[i][j] = 0
                        shark_dir[board[i][j]-1][0] = arr[d-1][p]
                        break
                else:
                    # 인접한 영역에 냄새가 0 인 곳이 없을 경우
                    for p in range(4):
                        dx, dy = dir[arr[d-1][p] - 1]
                        # 자기의 냄새인 영역
                        if -1 < i+dx < n and -1 < j+dy < n and smell[i+dx][j+dy][1] == board[i][j]:
                            nboard[i+dx][j+dy] = board[i][j]
                            nboard[i][j] = 0
                            shark_dir[board[i][j]-1][0] = arr[d-1][p]
                            break

    board = deepcopy(nboard)
    # 냄새 영역 하나씩 줄여주기
    for i in range(n):
        for j in range(n):
            if smell[i][j][1] != -1:
                smell[i][j][0] -= 1
                if smell[i][j][0] == 0:
                    smell[i][j] = [0,-1]
                            
    #print(board)
    #print(smell)
    cnt += 1

다른 풀이

import sys

input = sys.stdin.readline
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]

n, m, k = map(int, input().split())

smell, shark = [], [[] for _ in range(m)]
for i in range(n):
    smell.append(list(map(int, input().split())))
    for j in range(n):
        if smell[i][j]:
            shark[smell[i][j]-1].extend([i, j])
            smell[i][j] = [smell[i][j], k]

d = list(map(int, input().split()))
for i in range(m):
    shark[i].append(d[i]) #x, y, d

dir = [[] for _ in range(m)]
idx = -1
for i in range(4*m):
    if i % 4 == 0:
        idx += 1
    dir[idx].append(list(map(int, input().split())))

ans = 0
while True:
    ans += 1
    if ans == 1001:
        print(-1)
        break

    check = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        if shark[i] != 0:
            x, y, d, flag = shark[i][0], shark[i][1], shark[i][2], 0
            for j in range(4):
                ndir = dir[i][d-1][j]
                nx, ny = x + dx[ndir], y + dy[ndir]
                if 0 <= nx < n and 0 <= ny < n:
                    if smell[nx][ny] == 0:
                        flag = 1
                        break
            if flag == 0:
                for j in range(4):
                    ndir = dir[i][d-1][j]
                    nx, ny = x + dx[ndir], y + dy[ndir]
                    if 0 <= nx < n and 0 <= ny < n:
                        if smell[nx][ny][0] == i+1:
                            break

            if check[nx][ny]: #상어가 있는 경우
                if check[nx][ny] < i+1:
                    shark[i] =  #현재 상어 없애기
                else:
                    shark[check[nx][ny]-1] = 0 #자리 차지하는 상어 없애기
            else: #빈칸인 경우
                check[nx][ny] = i+1
                shark[i] = [nx, ny, ndir]

    for i in range(n):
        for j in range(n):
            if smell[i][j]:
                smell[i][j][1] -= 1
                if smell[i][j][1] == 0:
                    smell[i][j] = 0

    for i in range(m):
        if shark[i]:
            x, y = shark[i][0], shark[i][1]
            smell[x][y] = [i+1, k]

    if shark.count(0) == m-1:
        print(ans)
        break