23290번 - 마법사 상어와 복제

문제

23290번: 마법사 상어와 복제 (acmicpc.net)

23290번: 마법사 상어와 복제

풀이

물고기의 이동 제한 조건은 상어의 존재, 보드 경계 그리고 냄새이다.

냄새는 생성되는 턴에 한번, 그리고 그로부터 두턴 더 남아있기 때문에 총 세번의 반복문을 돌고나면 0이된다는 점에 주의하자.

상어는 최적의 이동경로를 먼저 탐색한 뒤 그 경로를 따라 이동한다. 경로 탐색은 이동경로에 있는 물고기 숫자의 합과 이동경로 자체에 의해 결정되는데, 이는 heapq를 이용하면 간단하게 구현가능하다. 주의할 점은 상어의 이동경로가 중복될 수 있다는 것인데, 따라서 방문여부로 백트래킹을 하면 안되고 3번 이동하면서 재방문한 칸에있는 물고기숫자는 재귀함수에 더해주지 않는 방식으로 구현해야한다.

import heapq

# W,NW,N,NE,E,SE,S,SW
dRow = [0,0,-1,-1,-1,0,1,1,1]
dCol = [0,-1,-1,0,1,1,1,0,-1]
# 상좌하우
dsx = [0,-1,0,1,0]
dsy = [0,0,-1,0,1]
P = ['','1','2','3','4']

M,S = map(int,input().split())
board = [[[] for row in range(5)] for col in range(5)]
for _ in range(M):
    fx,fy,d = map(int,input().split())
    board[fx][fy].append(d)
sx,sy = map(int,input().split())
smells = [[0]*5 for _ in range(5)]


def get_route(cnt,x,y,num,pth):
    if cnt >= 3:
        heapq.heappush(heap,((-num,int(pth)),pth))
        return
    for i in range(1,5):
        nx,ny = x+dsx[i],y+dsy[i]
        if 1 <= nx <= 4 and 1 <= ny <= 4:
            dnum = len_board[nx][ny]
            len_board[nx][ny] = 0
            get_route(cnt+1,nx,ny,num+dnum,pth+P[i])
            len_board[nx][ny] = dnum


for _ in range(S):
    # 복제 마법
    cpy = [[[*b] for b in a] for a in board]
    # 물고기 이동
    new_board = [[[] for row in range(5)] for col in range(5)]
    for row in range(1,5):
        for col in range(1,5):
            if board[row][col]:
                for i in range(len(board[row][col])):
                    d = board[row][col].pop()
                    for j in range(1,9):
                        nd = (8+d-j)%8+1
                        nRow,nCol = row+dRow[nd],col+dCol[nd]
                        if 1 <= nRow <= 4 and 1 <= nCol <= 4 and smells[nRow][nCol] == 0 and not (nRow == sx and nCol == sy):
                            new_board[nRow][nCol].append(nd)
                            break
                    else:
                        new_board[row][col].append(d)
    # 상어 이동경로 찾기
    len_board = [[len(b) for b in a] for a in new_board]
    heap = []
    get_route(0,sx,sy,0,'')
    # 상어 이동
    for i in map(int,heap[0][1]):
        sx += dsx[i]
        sy += dsy[i]
        if new_board[sx][sy]:
            new_board[sx][sy].clear()
            smells[sx][sy] = 3
    # 냄새 갱신, 마법 완료
    for row in range(1, 5):
        for col in range(1, 5):
            if smells[row][col] > 0:
                smells[row][col] -= 1
            board[row][col] = [*new_board[row][col]] + [*cpy[row][col]]


answer = 0
for row in range(1,5):
    for col in range(1,5):
        if board[row][col]:
            answer += len(board[row][col])
print(answer)