어른 상어 파이썬 백준 19237

문제

input

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

output

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

TODO

direction = [0,상,하,좌,우]
d = 1:상, 2:하, 3:좌, 4:우

딕셔너리 형태로 상어 아이디 별 방향 우선순위 저장.
아이디는 1~M
상어우선순위[id] = [방향우선순위_1, ..., 방향우선순위_4]

아이디 별 냄새 남기기
1초마다 -1 지금 상어가 있는 곳은 k로 설정
한 칸에 상어 아이디와 냄새 남은 시간 저장

[[id,k],[id,k-1]...]

상어 아이디 별 위치 저장
상어위치[id] = [x,y]
상어 방향 저장
상어방향 =[d1,d2,...,dm]

방향 고려해서 우선순위 별 상어 움직이기
상어 내쫓기 -> 상어 아이디 삭제

CODE

import sys 

n,m,k = map(int,sys.stdin.readline().split()) 
space = [list(map(int,sys.stdin.readline().split())) for _ in range(n)] # x번 상어 0은 빈칸 
shark_position = {}
for i in range(n):
    for j in range(n): 
        if space[i][j] != 0 : 
            shark_position[space[i][j]] = [i,j]
        space[i][j] = [space[i][j],0]
# 위, 아래, 좌 우 
shark_dir = list(map(int,sys.stdin.readline().split()))

shark_pri= {} 
for i in range (1,m+1): 
    shark_pri[i] = [0]
    for _ in range(4) : 
        shark_pri[i].append(list(map(int,sys.stdin.readline().split())))
    # 1상 2하 3좌 4우  우선순위
direction = [0,(-1,0),(1,0),(0,-1),(0,1)] 

def shark_move(shark_position,shark_pri, shark_dir,space):
    #n x n m마리 k초동안 냄새 유지
    t = 0 
    while t<=1000 and len(shark_position) >1 : 
        t+=1
        temp_space = [[0 for _ in range(n)] for _ in range(n)]
        len_shark_list = len(shark_position)
        shark_key_list = list(shark_position.keys())
        for q in range(len_shark_list): 
            key = shark_key_list[q]
            x,y = shark_position[key] 
            d = shark_dir[key-1]
            space[x][y][1] = k 
            change_first = False 
            change_second = False 
            tx,ty,td = 0,0,d
            for nd in shark_pri[key][d] : 
                px,py = direction[nd] 
                nx,ny = x+px,y+py 
                if 0<=nx<n and 0<=ny<n and space[nx][ny][0] ==0 : 
                    shark_position[key] = [nx,ny]
                    shark_dir[key-1] = nd
                    space[nx][ny][1] = -1 
                    if temp_space[nx][ny] == 0 : #상어 잡아먹기 
                        temp_space[nx][ny] = key 
                    else : 
                        if temp_space[nx][ny] < key : 
                            del shark_position[key]
                            
                        else : 
                            del shark_position[temp_space[nx][ny]]
                            temp_space[nx][ny] = key
                    change_first = True 
                    break 
                if 0<=nx<n and 0<=ny<n and not(change_first or change_second) and space[nx][ny][0] == space[x][y][0] : 
                    change_second = True 
                    tx,ty,td = nx,ny,nd 
            if (not change_first) and change_second : 
                shark_position[key] = [tx,ty] 
                shark_dir[key-1] = td 
                space[tx][ty][1] = -1 
                if temp_space[tx][ty] == 0 : 
                    temp_space[tx][ty] = key 
                else : 
                    if temp_space[tx][ty] < key : 
                        del shark_position[key] 
                    else : 
                        del shark_position[temp_space[tx][ty]]
        for i in range(n):
            for j in range(n): 
                if space[i][j][1] == -1 : 
                    space[i][j][1] = k 
                    space[i][j][0] = temp_space[i][j] 
                elif space[i][j][1] != 0 : 
                    space[i][j][1] -= 1
                    if space[i][j][1] == 0: 
                        space[i][j][0] = 0 
        
    return t 
t=shark_move(shark_position,shark_pri,shark_dir,space)            
if t != 1001 : 
    print(t)
else : 
    print(-1)

회고

방향 별 우선순위
냄새안나는곳 -> 자신의 냄새가 나는곳을 한 번에 처리하느라 머리가 아팟다
x,y
px,py -> plus x, plus y
nx,ny -> new x, new y
tx,ty -> temp x, temp y
문제가 너무 길고.. 구현문제는 디버깅하기 힘든건가 쉬운건가..