팩맨

지옥을 봤다....12시간 동안 풀었다...

 

엣지 케이스보다 '설계를 어떻게 할까?' 할 때 기본적인 사고 부터 틀려서 개고생해버렸다.

 

dfs를 bfs로 봐꾸는 것도 중요하지만 결국 반복적인 append, pop 작업을 dictionary로  덧뺄셈으로 바꿔서 통과했던 케이스.

 

import sys, copy, heapq
from collections import deque
from collections import defaultdict

m, t = map(int, sys.stdin.readline().strip().split())
r, c = map(int, sys.stdin.readline().strip().split())
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1], [0, -1, -1, -1, 0, 1, 1, 1]

p_dy , p_dx = [-1, 0, 1, 0], [0, -1, 0, 1]
p_r, p_c = r - 1, c - 1

monsters = [[defaultdict(int) for _ in range(4)] for _ in range(4)]
eggs = [[defaultdict(int) for _ in range(4)] for _ in range(4)]
deads = [[[] for _ in range(4)] for _ in range(4)]

max_monster_count = -1
roads = [0,0,0]

for idx in range(m): # 몬스터 참가
    r, c, d = map(int, sys.stdin.readline().strip().split())
    m_r, m_c, m_d = r - 1, c - 1, d - 1
    monsters[m_r][m_c][m_d] += 1
def check_monster_move_locations(y, x, d):
    global dy, dx, p_c, p_r, deads
    for i in range(8):
        ny = y + dy[(d + i) % 8]
        nx = x + dx[(d + i) % 8]
        if ny >= 4 or ny < 0 or nx >= 4 or nx < 0:
            continue
        if (p_r == ny and p_c == nx) or len(deads[ny][nx]) != 0:
            continue
        return (ny, nx), (d + i) % 8
    return False

def move_monsters():
    global monsters
    tmp_moster_graph = [[defaultdict(int) for _ in range(4)] for _ in range(4)]
    for y in range(4):
        for x in range(4):
            for d in monsters[y][x]:
                checked_info = check_monster_move_locations(y, x, d)
                if not checked_info:
                    tmp_moster_graph[y][x][d] += monsters[y][x][d]
                    continue
                else:
                    ny, nx = checked_info[0]
                    next_d = checked_info[1]
                    tmp_moster_graph[ny][nx][next_d] += monsters[y][x][d]
    monsters = tmp_moster_graph

    return
    
def egg_complete():
    global monsters, eggs
    for y in range(4):
        for x in range(4):
            for d in eggs[y][x]:
                if d not in monsters[y][x]:
                    monsters[y][x][d] = eggs[y][x][d]
                else:
                    monsters[y][x][d] += eggs[y][x][d]

def remove_monster(y, x):
    global p_dx, p_dy, p_r, p_c, monsters, deads, roads, max_monster_count
    for d in roads:
        y = y + p_dy[d]
        x = x + p_dx[d]
        if len(monsters[y][x]) != 0:
            deads[y][x].append(3)
        monsters[y][x] = defaultdict(int)
        
    p_r, p_c = y, x
    max_monster_count = -1

def remove_dead():
    global deads
    for y in range(4):
        for x in range(4):
            deads[y][x] = [d - 1 for d in deads[y][x] if d > 1]

def find_p_m_road(y, x, move_count, monster_count, road, monster_graph):
    global p_dy, p_dx, max_monster_count, roads

    q = deque([])
    q.append((y, x, move_count, monster_count, road, monster_graph))

    while q:
        y, x, move_count, monster_count, road, monster_graph = q.popleft()
        if move_count == 3:
            if max_monster_count < monster_count:
                max_monster_count = monster_count
                roads = road
            continue
        
        for d in range(4):
            ny = y + p_dy[d]
            nx = x + p_dx[d]
            if ny >= 4 or nx >= 4 or ny < 0 or nx < 0:
                continue
            add_count = 0
            for i in monster_graph[ny][nx]:
                add_count += monster_graph[ny][nx][i]
            tmp_graph = copy.deepcopy(monster_graph)
            tmp_graph[ny][nx] = []
            q.append((ny, nx, move_count + 1, monster_count + add_count, road + [d], tmp_graph))

def move_p_m():
    global p_r, p_c, roads, monsters
    find_p_m_road(p_r, p_c, 0, 0, [], monsters)
    remove_monster(p_r, p_c)

def make_egg():
    global monsters, eggs
    eggs = monsters

while t != 0: #턴수 만큼 진행
    make_egg()  
    move_monsters()
    move_p_m()
    remove_dead()
    egg_complete()
    t -= 1
answer = 0

for y in range(4):
    for x in range(4):
        for i in monsters[y][x]:
            answer += monsters[y][x][i]
print(answer)