19237번 - 어른 상어

문제

 

19237번: 어른 상어 (acmicpc.net)

19237번: 어른 상어

풀이 1

상어가 매번 이동할 때 마다 "냄새 값"이 1씩 줄어드는데, 어렵게 생각할 필요 없이, 매 초마다 모든 냄새 값을 1씩 빼준 뒤 상어가 위치하는 곳에 냄새 값을 K로 갱신해주면 된다.

while 문 안에 들어가는 로직만 잘 설계하면 생각보다 어렵지는 않은 문제이다.

import heapq

# 북,남,서,동
dRow = [-1,1,0,0]
dCol = [0,0,-1,1]

N,M,K = map(int,input().split())
sharks = [[0]*N for _ in range(N)]
smells = [[[0,0] for row in range(N)] for col in range(N)]
for row in range(N):
    for col,v in enumerate(map(int,input().split())):
        if v > 0:
            sharks[row][col] = v
            smells[row][col][0],smells[row][col][1] = v,K
dirs = [-1]+list(map(lambda x : int(x) - 1,input().split()))
priorities = [[] for _ in range(M+1)]
for i in range(1,M+1):
    for _ in range(4):
        priorities[i].append(list(map(lambda x : int(x)-1,input().split())))

answer = 0
cnt = M
while True:
    # 상어 이동
    visited = [[0]*N for _ in range(N)]
    for row in range(N):
        for col in range(N):
            if sharks[row][col] > 0 and visited[row][col] == 0:
                visited[row][col] = 1
                shark = sharks[row][col]
                dir = dirs[shark]
                heap = []
                for i,v in enumerate(priorities[shark][dir]):
                    nRow,nCol = row+dRow[v],col+dCol[v]
                    smell = 0
                    if 0 <= nRow < N and 0 <= nCol < N:
                        if smells[nRow][nCol][0] == shark:
                            smell = 1
                        elif smells[nRow][nCol][0] > 0:
                            smell = 2
                        heapq.heappush(heap,((smell,i),v,nRow,nCol))
                dir,nRow,nCol = heap[0][1:]
                sharks[row][col] = 0
                if sharks[nRow][nCol] == 0 or (sharks[nRow][nCol] > 0 and shark < sharks[nRow][nCol]):
                    if sharks[nRow][nCol] > 0:
                        cnt -= 1
                    visited[nRow][nCol] = 1
                    dirs[shark] = dir
                    sharks[nRow][nCol] = shark
                elif sharks[nRow][nCol] < shark:
                    cnt -= 1
    # 상어 냄새 갱신
    for row in range(N):
        for col in range(N):
            if smells[row][col][0] > 0:
                smells[row][col][1] -= 1
                if smells[row][col][1] == 0:
                    smells[row][col][0] = 0
    # 상어 냄새 뿌리기
    for row in range(N):
        for col in range(N):
            if sharks[row][col] > 0:
                smells[row][col][0], smells[row][col][1] = sharks[row][col], K
    answer += 1
    if cnt <= 1:
        print(answer)
        break
    elif answer >= 1000:
        print(-1)
        break

풀이 2

다음 이동 위치를 탐색할 때 우선순위큐를 이용하는 문제이다.

import heapq

# 북 남 서 동
dRow = [0,-1,1,0,0]
dCol = [0,0,0,-1,1]

N,M,K = map(int,input().split())
board = []
# 상어 번호, 남은 시간
smells = [[[0,0] for col in range(N)] for row in range(N)]
for _ in range(N):
    board.append(list(map(int,input().split())))
dirs = [0] + list(map(int,input().split()))
# 상어 번호 -> 방향
priority = [[]]
for _ in range(M):
    li = [[]]
    for __ in range(4):
        li.append(list(map(int,input().split())))
    priority.append(li)

cnt = M
for t in range(1,1001):
    # 냄새 뿌리기
    for row in range(N):
        for col in range(N):
            if board[row][col] > 0:
                smells[row][col] = [board[row][col],K]
    # 탐색 후 이동
    new_board = [[0]*N for _ in range(N)]
    for row in range(N):
        for col in range(N):
            if board[row][col] > 0:
                # 탐색
                heap = []
                idx = board[row][col]
                dir = dirs[idx]
                smell = 2
                for i,ndir in enumerate(priority[idx][dir]):
                    nRow,nCol = row+dRow[ndir],col+dCol[ndir]
                    if 0 <= nRow < N and 0 <= nCol < N:
                        if smells[nRow][nCol][0] == 0:
                            smell = 0
                        elif smells[nRow][nCol][0] == idx:
                            semll = 1
                        else:
                            continue
                        heapq.heappush(heap,(smell,i,nRow,nCol,ndir))
                if heap:
                    # 이동
                    nr,nc,nd = heap[0][2:]
                    dirs[idx] = nd
                    # 동족상잔
                    target = new_board[nr][nc]
                    if target > 0:
                        new_board[nr][nc] = idx if idx < target else target
                        cnt -= 1
                    else:
                        new_board[nr][nc] = idx
                else:
                    new_board[row][col] = idx
    board = new_board
    # 냄새 갱신
    for row in range(N):
        for col in range(N):
            if smells[row][col][0] > 0:
                smells[row][col][1] -= 1
            if smells[row][col][1] == 0:
                smells[row][col][0] = 0
    if cnt == 1:
        print(t)
        break
else:
    print(-1)