[백준] 19237. 어른 상어

https://www.acmicpc.net/problem/19237

19237번: 어른 상어

이번에도 deepcopy를 이용해서 원래 맵을 복사해주고, 복사본으로 작업한 뒤 이를 원래 맵에 덮어씌우는 식으로 진행해야 간편하게 풀리는 문제였다. 일단 2차원 리스트를 가지고 이것저것 작업해야하는 문제는 무조건 deepcopy로 배열을 복사해두고 푸는 걸 제일 우선으로 생각해야겠다.

 

문제가 길고, 설명이 복잡해서 처음에 문제 이해하는 데에만 오래 걸렸는데 이 역시도 구현하라는 대로만 구현하면 쉽게 통과된다. smell 배열을 따로 만들어서 관리해주었으며, k초가 지나면 냄새가 사라지므로 각 배열의 원소를 [초, 상어 번호]로 지정해주어서 1초가 지날 때마다 초를 감소시켜주고 0이 되면 냄새를 없애 주었다. 아무 냄새도 없는 경우는 [-1, 0]으로 나타냈다.

 

남은 상어가 1마리일 경우 while문을 탈출하므로 left_shark 변수를 따로 만들어서 같은 칸에 여러마리 상어가 있을 경우 숫자가 큰 상어를 없애며 left_shark를 감소시켜주었다. 또한 1000초가 넘어가면 -1을 출력해야 하므로 isFalse 변수를 이용해 이를 확인했다.

 

dy, dx 는 위, 아래, 왼쪽, 오른쪽 순서이며 dir 숫자에 맞춰서 0번 인덱스에 0, 0 으로 초기화하려다가 그냥 방향 - 1을 해줬다. 상어가 바라보는 방향을 기준으로 우선순위대로 방향을 확인하며 냄새가 없는 칸이라면 이동 후 for문을 탈출한다. 만약 for문을 탈출하지 못했다면 상어 주변에 냄새가 없는 칸이 없다는 뜻이고, 이는 else 문에서 자신과 같은 냄새를 가진 칸으로 이동하여 해결해준다. 모든 상어의 이동이 끝나면 위에서 언급한 냄새 줄이기를 해준다.

 

import sys
from copy import deepcopy
input = sys.stdin.readline

N, M, k = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(N)]
time = 0
shark_priority = [[] for _ in range(M+1)]
# 1: 위, 2: 아래, 3: 왼쪽, 4 : 오른쪽
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
shark_dir = list(map(int, input().split()))
for i in range(1, M+1):
    shark_priority[i] = [list(map(int, input().split())) for _ in range(4)]

smell = [[[-1, 0] for _ in range(N)] for _ in range(N)]
isFalse = False
left_shark = M

while True:
    if left_shark == 1:
        break

    if time >= 1000:
        isFalse = True
        break

    for i in range(N):
        for j in range(N):
            if grid[i][j]:
                smell[i][j] = [k, grid[i][j]]

    new_grid = deepcopy(grid)
    for i in range(N):
        for j in range(N):
            if grid[i][j]:
                now_shark = grid[i][j]
                now_dir = shark_dir[now_shark-1]
                for d in shark_priority[now_shark][now_dir-1]:
                    ny = i + dy[d-1]
                    nx = j + dx[d-1]
                    if 0 <= ny < N and 0 <= nx < N and smell[ny][nx] == [-1, 0]:
                        if new_grid[ny][nx] == 0 :
                            new_grid[ny][nx] = now_shark
                            new_grid[i][j] = 0
                        else:
                            if new_grid[ny][nx] > now_shark:
                                new_grid[ny][nx] = now_shark
                            left_shark -= 1
                            new_grid[i][j] = 0
                        shark_dir[now_shark-1] = d
                        break
                else: # 냄새가 없는 칸이 하나도 없을 경우
                    for d in shark_priority[now_shark][now_dir-1]:
                        ny = i + dy[d - 1]
                        nx = j + dx[d - 1]
                        if 0 <= ny < N and 0 <= nx < N and smell[ny][nx][1] == now_shark:
                            new_grid[ny][nx] = now_shark
                            new_grid[i][j] = 0
                            shark_dir[now_shark - 1] = d
                            break

    grid = deepcopy(new_grid)

    # 냄새 줄여주기
    for i in range(N):
        for j in range(N):
            if smell[i][j][0] != -1:
                smell[i][j][0] -= 1
            if smell[i][j][0] == 0:
                smell[i][j] = [-1, 0]

    time += 1

if isFalse:
    print(-1)

else:
    print(time)