[백준 19237번] 어른 상어

문제 링크

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

19237번: 어른 상어

 

풀이

백준 상어 문제들은 다 복잡한 것 같다.. 

graph : 상어 번호와 남은 냄새 시간을 저장한다. 

shark : 상어의 번호가 key, 위치와 방향을 value로 저장한다. 

priorites : 상어의 방향 별 우선 순위를 저장한다. 

 

시간이 1000초 이하일 때까지 아래 과정을 반복한다. 

1. 낮은 번호부터, 상어 별 현재 위치에 냄새를 뿌릴 수 있는지 체크한다. 

- 빈 곳이거나, 같은 냄새가 있다면 뿌릴 수 있음 

- 둘 다 불가능하면 제거 

 

2. 낮은 번호부터, 상어 별 현재 방향 별, 우선 순위 방향에 따라 이동한다. 

- 빈 곳이면 냄새 뿌리기

- 빈 곳이 없다면, 자기 냄새와 같은 곳에 냄새 뿌리기 

- 둘 다 불가능하면 제거 

 

3. 냄새가 있는 곳 유지 시간 줄이기 

- graph에서 냄새가 있다면 유지 시간을 -1 한다. 

- 유지 시간이 0이 되었다면, 냄새 제거한다.

 

4. 시간 +1

 

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

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

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))
    
# 상어의 위치와 초기방향을 딕셔너리로 저장 
shark = {}

# 위 아래 왼쪽 오른쪽 
dx =[-1,1,0,0]
dy = [0,0,-1,1]

# 상어의 초기 방향 
direct = list(map(int,input().split()))

for i in range(n):
    for j in range(n):
        if graph[i][j] != 0 :
            # 상어의 현재 위치, 초기 방향 저장 
            shark[graph[i][j]] = (i, j,  direct[graph[i][j]-1])
        graph[i][j] = None
        
# 상어의 방향 별 우선 순위 ( 위 아래 왼쪽 오른쪽 )
priorities = []

for _ in range(m*4):
    priorities.append(list(map(int,input().split())))
    
time = -1
while time <= 1000:
    
    # 1번 상어만 남았다면 중단 
    if len(shark) == 1 :
        print(time)
        exit(0)

    key = list(shark.keys())
    # 번호가 빠른 상어부터 이동 
    key.sort()
    
    # 자신의 위치에 냄새를 뿌림 
    for idx in key:
        # 비었으면 
        if graph[shark[idx][0]][shark[idx][1]] is None :
            # 상어 번호, 남은 냄새 시간 기록 
            graph[shark[idx][0]][shark[idx][1]] = [idx, k]
        # 자신의 냄새와 같다면, 
        elif graph[shark[idx][0]][shark[idx][1]][0] == idx:
            graph[shark[idx][0]][shark[idx][1]] = [idx,k]
        # 이미 상어가 있거나, 자신의 냄새와 달라서 이동할 수 없다면 
        else :
            del shark[idx]
        
    key  = list(shark.keys())
    key.sort()
    
    # 상어 이동 
    for idx in key:
        # 현재 위치와 방향 
        x, y, d = shark[idx]
        # 빈 곳으로 이동 가능한지 체크
        flag_blank = False
        
        for i in priorities[(idx-1) * 4 + (d-1)]:
            nx = x + dx[i-1]
            ny = y + dy[i-1]
            nd = i 
            
            if 0<=nx<n and 0<=ny<n:
                # 비어있으면 이동 가능 
                if graph[nx][ny] is None:
                    flag_blank = True 
                    # 상어 위치 갱신 
                    shark[idx] = [nx,ny,nd]
                    break 
        
        # 자신의 냄새와 같은 곳으로 이동 가능한지 체크         
        flag_same = False 
        
        if not flag_blank:
            for i in priorities[(idx-1) * 4 + (d-1)]:
                nx = x + dx[i-1]
                ny = y + dy[i-1]
                nd = i 
                
                if 0<= nx < n and 0<= ny < n:
                    if graph[nx][ny][0] == idx :
                        flag_same = True 
                        # 상어 위치 갱신 
                        shark[idx] = [nx,ny,nd]
                        break
        else :
            continue 
        # 빈 곳, 자신의 냄새와 같은 곳도 없다면 삭제 
        if not flag_same :
            del shark[idx]
            
    for i in range(n):
        for j in range(n):
            # 상어가 위치에 있다면 냄새 유지 횟수 줄이기 
            if graph[i][j] is not None:
                graph[i][j][1] -= 1 
                # 냄새 사라짐 
                if graph[i][j][1] == 0:
                    graph[i][j] = None 
    
    time +=1 
    
print(-1)