★Implementation&Simluation Upper-Advanced I - 1 Solved★

★ 19237 어른 상어 ★

 

import sys
input=sys.stdin.readline
from collections import deque

N,M,k=map(int,input().split()) #NxNsize / M sharks / smell limit k
trace=[]
smell=[[0]*N for _ in range(N)]
sharks=deque()
shark_ds_priorities=[]
#shark_ds
dx,dy=['?',-1,1,0,0],['?',0,0,-1,1]
num_of_sharks=M

for i in range(N):
    l=list(map(int,input().split()))
    trace.append(l)
    for j in range(N):
        if l[j] != 0:
            sharks.append((i,j,l[j])) #x,y,shark_num
            smell[i][j] = k

shark_ds=list(map(int,input().split())) 

for _ in range(M):
    d=[]
    for _ in range(4):
        d.append(list(map(int,input().split())))
    shark_ds_priorities.append(d)

time=0
while 1:
    #spread smell
    for shark in sharks:
        smell[shark[0]][shark[1]] = k
    
    #move
    for _ in range(len(sharks)):
        x,y,num = sharks.popleft()

        #in shark-d priorities
        moved,my_trace=False,[]
        for next_d in shark_ds_priorities[num-1][shark_ds[num-1]-1]:
            nx,ny=x+dx[next_d],y+dy[next_d]
            if 0<=nx<N and 0<=ny<N:
                if smell[nx][ny] > 0: #if smell
                    if trace[nx][ny] == num: #if this is my trace
                        my_trace.append((nx,ny))
                    continue
                else: #if no smell -> move!
                    moved=True
                    sharks.append((nx,ny,num))
                    shark_ds[num-1]=next_d
                    break
        if not moved:
            nx,ny=my_trace[0][0],my_trace[0][1] #move to my trace(the 1st one in the list - based on priority)
            sharks.append((nx,ny,num))
            if nx==(x-1):
                shark_ds[num-1]=1
            elif nx==(x+1):
                shark_ds[num-1]=2
            elif ny==(y-1):
                shark_ds[num-1]=3
            else:
                shark_ds[num-1]=4
    
    #disappear smell
    for x in range(N):
        for y in range(N):
            if smell[x][y] > 0:
                smell[x][y] -=1
                if smell[x][y] == 0:
                    trace[x][y] = 0
    
    #after moving
    shark_list=[]
    while sharks:
        x,y,num = sharks.popleft()

        if trace[x][y] == 0: #no shark exists
            trace[x][y] = num
            shark_list.append((x,y,num))
        else: #if shark exists
            if num < trace[x][y]: #mine has more priority
                shark_list.remove((x,y,trace[x][y]))
                trace[x][y]=num
                num_of_sharks-=1
                shark_list.append((x,y,num))
            elif trace[x][y] < num:
                num_of_sharks-=1
            else: #trace[x][y] == num
                shark_list.append((x,y,num))
    for shark in shark_list:
        sharks.append(shark)
    time+=1
    if num_of_sharks == 1:
        print(time)
        break
    if time >= 1000:
        print(-1)
        break

 

✈️ 

① trace: 상어가 위치한 상태 (2차원 배열)

② smell: 각 상어의 smell 현황 (2차원 배열) 

③ sharks: deque() 준비: (x,y,shark_num) 형태로 각 shark마다 deque에 넣기 (deque)

④ shark_ds: 각 상어의 현 방향 주어짐 (1차원 list)

⑤ shark_ds_priorities: 각 상어의 상/하/좌/우에 따른 방향 우선순위 (2차원 배열)

 

✈️ 진행

" 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다 "

① sharks deque에 있는 각 모든 현재 shark의 (x,y)에 smell k 뿌리기 (smell[shark[0]][shark[1]] = k)

while 1:
    #spread smell
    for shark in sharks:
        smell[shark[0]][shark[1]] = k

---

" 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, "

② len(sharks)만큼 sharks deque에서 shark 꺼내면서 shark 실제 이동

: shark_ds_priorities에 따라 nx,ny = x + dx[next_d], y + dy[next_d] update

#move
for _ in range(len(sharks)):
    x,y,num = sharks.popleft()

    #in shark-d priorities
    moved,my_trace=False,[]
    for next_d in shark_ds_priorities[num-1][shark_ds[num-1]-1]:
        nx,ny=x+dx[next_d],y+dy[next_d]

---

" 각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다 "

③ 일단, nx와 ny가 0이상 N미만인 지 (즉 범위 내에 있는 지) 확인 후, 아무 냄새가 없다면 바로 이동! (아래의 else문)

if 0<=nx<N and 0<=ny<N:
    if smell[nx][ny] > 0: #if smell
        if trace[nx][ny] == num: #if this is my trace
            my_trace.append((nx,ny))
        continue
    else: #if no smell -> move!
        moved=True
        sharks.append((nx,ny,num))
        shark_ds[num-1]=next_d
        break

→ 이동했으므로  moved = True / sharks deque에 update한 (nx,ny,num) append / shark_ds next_d 방향으로 update

---

" 인접한 칸 중 아무 냄새가 없는 칸의 방향이 없다면 자신의 냄새가 있는 칸의 방향으로 잡는다 "

④ 냄새가 있다면(아래 if smell[nx][ny]>0) trace list에 (nx,ny) append (위 ③ 코드와 중복)

if smell[nx][ny] > 0: #if smell
    if trace[nx][ny] == num: #if this is my trace
        my_trace.append((nx,ny))
    continue

---

⑤ 아무 냄새가 없는 칸이 없다면(moved=False) my_trace []의 첫번째 원소에 따라 move / shark_ds update

if not moved:
    nx,ny=my_trace[0][0],my_trace[0][1] #move to my trace(the 1st one in the list - based on priority)
    sharks.append((nx,ny,num))
    if nx==(x-1):
        shark_ds[num-1]=1
    elif nx==(x+1):
        shark_ds[num-1]=2
    elif ny==(y-1):
        shark_ds[num-1]=3
    else:
        shark_ds[num-1]=4

---

⑥ 이동 후, 각 격자의 냄새가 1씩 사라진다.

#disappear smell
for x in range(N):
    for y in range(N):
        if smell[x][y] > 0:
            smell[x][y] -=1
            if smell[x][y] == 0:
                trace[x][y] = 0

★ 이 때 주의점! 냄새가 0이 된다는 건 상어가 사라진다는 뜻. 그 때는 trace[x][y] = 0으로 설정해 상어를 사라지게 해야 함 ★

---

" 모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다. "

⑦ shark_list [] 만들고 각 shark 우선순위에 따라 제거하거나 update / 맨 마지막에 shark_list를 deque에 넣기

#after moving
shark_list=[]
while sharks:
    x,y,num = sharks.popleft()

    if trace[x][y] == 0: #no shark exists
        trace[x][y] = num
        shark_list.append((x,y,num))
    else: #if shark exists
        if num < trace[x][y]: #mine has more priority
            shark_list.remove((x,y,trace[x][y]))
            trace[x][y]=num
            num_of_sharks-=1
            shark_list.append((x,y,num))
        elif trace[x][y] < num:
            num_of_sharks-=1
        else: #trace[x][y] == num
            shark_list.append((x,y,num))
for shark in shark_list:
    sharks.append(shark)

---

⑧ 전 과정이 끝났으므로 time +=1 / num_of_sharks == 1, 즉 1번 상어 1마리만 남거나 1000초 이상이면 print(time) 하고 프로그램 종료.

time+=1
if num_of_sharks == 1:
    print(time)
    break
if time >= 1000:
    print(-1)
    break

---

---