[파이썬/python] 백준 - 19237 어른 상어

문제

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

---

문제 설명

1. N*N 크기의 격자에 M마리의 상어가 존재한다.
2. 상어들은 자신들의 위치를 냄새를 뿌리고 시작한다.
3. 상어들은 한 번에 여러 행동들을 수행한다.
   1. 모든 상어가 우선순위에 맞게 동시에 상하좌우로 이동한다.
      1. 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 이동한다.
      2. 냄새가 전부 있다면, 자신의 냄새가 있는 칸의 방향으로 이동한다.
      3. 이 때 가능한 칸이 여러개라면 입력으로 주어진 우선순위에 맞게 이동한다.
      4. *참고로 상어가 이동할 수 없는 경우는 존재하지 않는다.
   2. 이동 후 현재 위치에 자신의 냄새를 뿌린다.
      1. 냄새는 K번 이동 후 사라진다.
4. 이동을 마쳤을 때 같은 위치에 여러 마리의 상어가 존재하면, 번호가 낮은 상어를 제외하고 전부 쫒겨난다.

---

풀이

상어 문제 중에 그나마 직관적인 문제여서 머리로 생각한 대로 그대로 구현해서 맞았다.

다만 상어의 수를 입력할 때 받은 변수 M으로 컨트롤하다가, 반복문에서 M 변수를 사용하여 오류가 생기는 문제를 겪어서 좀 난항했다.

그리고 문제에서 명확하게 나와 있지 않아서 헷갈렸는데, 상어가 이동 불가한 경우는 없다. 인접한 칸에 냄새가 모두 존재하고 자신의 냄새가 없을 때 상어가 이동 불가능한 것이 아닌가 했는데, 게시판을 검색해 보니 상어는 무조건 이동을 할 수 있는 경로로만 주어진다고 한다.. 왜 문제에는 명시를 해주지 않았는지 모르겠다.

 

1. 해시를 통해 각 상어의 좌표와 냄새 위치를 저장한다.
2. move()메서드를 통해 1번 상어부터 순차적으로 이동한다.
   1. 이 때 이전 이동과 겹치지 않기 위해 next_shark 딕셔너리를 생성해 다음 위치들을 저장해준다.
   2. 이동한 위치가 냄새가 없다면 path 0번째 인덱스에 저장, 이동한 위치에 냄새가 있고, 나의 냄새라면 path 1번째 인덱스에 저장한다.
   3. 이동 가능한 우선순위에 맞게 상어를 이동한다.
3. 모든 상어의 이동을 마치고 냄새를 1 감소시킨다.
4. 이동한 상어의 현재 위치에서 냄새를 뿌린다.
5. 2-4 과정을 1000회 반복하면서 1000회 내에 1번 상어만 남았다면 현재 초를 출력하고, 아니라면 -1을 출력한다.

---

코드

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

#상하좌우
dy = [0,-1,1,0,0]
dx = [0,0,0,-1,1]


shark = dict()
cnt = 0
N,M,K = map(int,input().split())
total_shark = M
smell = {}
for y in range(N):
    tmp = list(map(int,input().split()))
    for x in range(N):
        if tmp[x]:
            shark[tmp[x]] = (y,x)
            smell[(y,x)] = [tmp[x],K]
crnt_d = [0] + list(map(int,input().split()))

sd = [[] for _ in range(M+1)]
for i in range(1,M+1):
    sd[i] = [0] + [list(map(int,input().split())) for _ in range(4)]

def move():
    global total_shark
    #1번 상어부터 순차적으로 이동
    next_shark = dict()
    for i in range(1,M+1):
        if crnt_d[i] == -1:
            continue
        cd = crnt_d[i]
        y,x = shark[i]
        path = [[],[]]
        for j in sd[i][cd]:
            ny = y + dy[j]
            nx = x + dx[j]
            if ny < 0 or ny > N-1 or nx < 0 or nx > N-1:
                continue
            if (ny,nx) in smell:
                #나의 냄새가 아니라면
                if smell[(ny,nx)][0] != i:
                    continue
                else:
                    path[1].append((ny,nx,j))
            else:
                path[0].append((ny,nx,j))
        if path[0]:
            py,px,dir = path[0][0][0],path[0][0][1],path[0][0][2]
        else:
            py,px,dir = path[1][0][0],path[1][0][1],path[1][0][2]

        if (py,px) in next_shark:
            next_shark[(py,px)].append([i,dir])
        else:
            next_shark[(py,px)] = [[i,dir]]

    for i in next_shark.keys():
        if len(next_shark[i]) > 1:
            for j in range(1,len(next_shark[i])):
                ns,ndir = next_shark[i][j]
                crnt_d[ns] = -1
                total_shark-=1
                shark.pop(ns)
        crnt_d[next_shark[i][0][0]] = next_shark[i][0][1]
        shark[next_shark[i][0][0]] = i
    #냄새 없애기
    smell_keys = deepcopy(list(smell.keys()))
    for k in smell_keys:
        smell[k][1] -= 1
        if smell[k][1] == 0:
            smell.pop(k)
    #냄새 뿌리기
    for i in range(1,M+1):
        if crnt_d[i] == -1:
            continue
        y,x = shark[i]
        smell[(y,x)] = [i,K]


for s in range(1,1001):
    move()
    if total_shark == 1 and crnt_d[1] != -1:
        print(s)
        exit()
print(-1)

---

시간복잡도

• 총 M개의 상어를 이동, 이동하는 로직 중, 냄새를 제거할 때 최대 $N*N$번 탐색(가장 큰 계수)한다.
• 따라서 약 $O(N*N*M) = O(20*20*400) = O(10^5)$의 시간복잡도가 소요된다.