코드트리 빵

갈수록 코테가 어려워 지는 것 같다...

우선 시간에 따라 통과하지 못하는 길목이 생기는데, 이를 고려해서 경로를 탐색해줘야한다.

이를 재탐색 하는결과로 출력해서 실패를 겪었다.

도착시간에 맞춰 통과못하는 부분을 주석처리하니 성공.

2시간 정도 걸렸.. 갈수록 어렵다.

 

실패코드

import copy
import sys, math
from collections import deque

n, m = map(int, sys.stdin.readline().split())
time = 0
graph = []
b_location = []
c_location = []
infos = []
dx, dy = [0,0,-1,1], [-1,1,0,0]
alive_infos = []
answer = 0

def search_excute_time(start, end):
    global graph, dx, dy, n
    least_time = []
    tmp_graph = [[math.inf for _ in range(n)] for _ in range(n)]
    for y in range(len(graph)):
        for x in range(len(graph[y])):
            if graph[y][x] == 3:
                tmp_graph[y][x] = False
    q = deque([])
    sy, sx = start
    tmp_graph[sy][sx] = 0
    q.append(start)

    while q:
        y, x = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx >= n or nx < 0 or ny >= n or ny < 0:
                continue
            if not tmp_graph[ny][nx]:
                continue
            if tmp_graph[y][x] + 1 < tmp_graph[ny][nx]:
                tmp_graph[ny][nx] = tmp_graph[y][x] + 1
                q.append((ny, nx))
    ey, ex = end
    return tmp_graph[ey][ex]

def find_near_c(by, bx):
    global c_location
    near_c_location = (math.inf, math.inf)
    for cy, cx in c_location:
        if abs(near_c_location[0] - by) + abs(near_c_location[1] - bx) > abs(by - cy) + abs(bx - cx):
            near_c_location = (cy, cx)
    c_location.remove(near_c_location)
    return near_c_location

for y in range(n):
    peice_graph = list(map(int, sys.stdin.readline().split()))
    for x in range(len(peice_graph)):
        if peice_graph[x] == 1:
            c_location.append((y, x))
    graph.append(peice_graph)

for _ in range(m):
    y, x = map(int, sys.stdin.readline().split())
    b_location.append((y - 1, x - 1))

for idx in range(len(b_location)):
    by, bx = b_location[idx]
    infos.append([idx + 1, (by, bx), find_near_c(by, bx)])


while infos:
    time += 1
    for alive_info in alive_infos:
        if alive_info[0] == time:
            y, x = alive_info[1]
            graph[y][x] = 3

    for info in infos:
        if time == info[0]:
            y, x  = info[2]
            graph[y][x] = 3
            alive_time = search_excute_time(info[2], info[1])
            alive_infos.append((time + alive_time, info[1]))
            answer = max(answer, time + alive_time)
            infos.pop(0)
print(answer)

 

import copy
import sys, math
from collections import deque
from collections import defaultdict
n, m = map(int, sys.stdin.readline().split())
time = 0
graph = []
b_location = []
c_location = []
infos = []
dx, dy = [0,0,-1,1], [-1,1,0,0]
alive_infos = []
answer = 0
least_time = defaultdict(int)

def search_excute_time(start, end):
    global graph, dx, dy, n
    tmp_graph = [[math.inf for _ in range(n)] for _ in range(n)]
    for y in range(len(graph)):
        for x in range(len(graph[y])):
            if graph[y][x] == 3:
                tmp_graph[y][x] = False
    q = deque([])
    sy, sx = start
    tmp_graph[sy][sx] = 0
    q.append(start)

    while q:
        y, x = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx >= n or nx < 0 or ny >= n or ny < 0:
                continue
            if not tmp_graph[ny][nx]:
                continue
            if tmp_graph[y][x] + 1 < tmp_graph[ny][nx]:
                tmp_graph[ny][nx] = tmp_graph[y][x] + 1
                q.append((ny, nx))
    ey, ex = end
    return tmp_graph[ey][ex]

def find_near_c(by, bx):
    global c_location
    near_c_location = (math.inf, math.inf)
    for cy, cx in c_location:
        if abs(near_c_location[0] - by) + abs(near_c_location[1] - bx) > abs(by - cy) + abs(bx - cx):
            near_c_location = (cy, cx)
    c_location.remove(near_c_location)
    return near_c_location

for y in range(n):
    peice_graph = list(map(int, sys.stdin.readline().split()))
    for x in range(len(peice_graph)):
        if peice_graph[x] == 1:
            c_location.append((y, x))
    graph.append(peice_graph)

for _ in range(m):
    y, x = map(int, sys.stdin.readline().split())
    b_location.append((y - 1, x - 1))

for idx in range(len(b_location)):
    least_time[idx + 1] = math.inf
    by, bx = b_location[idx]
    infos.append([idx + 1, (by, bx), find_near_c(by, bx)])


while infos:
    time += 1
    # for alive_info in alive_infos:
    #     print(alive_info)
    #     if alive_info[0] == time:
    #         y, x = alive_info[1]
    #         graph[y][x] = 3

    for info in infos:
        if time == info[0]:
            y, x  = info[2]
            graph[y][x] = 3
            alive_time = search_excute_time(info[2], info[1])
            alive_infos.append((time + alive_time, info[1]))
            answer = max(answer, time + alive_time)
            infos.pop(0)
print(answer)