코드트리 - 코드트리 빵 (파이썬, Python)

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
combini = []
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    combini.append((a, b))

# 편의점에 사람 배치
def Batch_Basecamp(x, y):
    Q = deque()
    Q.append((x, y))
    visit = [[0]*n for _ in range(n)]
    visit[x][y] = 1
    distance = [[0]*n for _ in range(n)]
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    temp = []
    while Q:
        x, y = Q.popleft()
        if graph[x][y] == 1:
            temp.append((x, y, distance[x][y]))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != -1 and visit[nx][ny] == 0:
                visit[nx][ny] = 1
                distance[nx][ny] = distance[x][y] + 1
                Q.append((nx, ny))

    return sorted(temp, key=lambda x:(-x[2], -x[0], -x[1]))

#현재 사람이 목적지까지 가기
def go_combini(x, y, ex, ey):
    Q = deque()
    Q.append((x, y))
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    temp = []
    arr = cal_dist(ex, ey)
    while Q:
        x, y = Q.popleft()
        distance = int(1e9)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != -1:
                dist = arr[nx][ny]
                temp.append((nx, ny, dist))

    return sorted(temp, key=lambda x:(-x[2], -x[0], -x[1]))

# 목적지부터 현재 사람 위치 거리 계산을 위한 함수
def cal_dist(x, y):
    Q = deque()
    Q.append((x, y))
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    visit = [[0]*n for _ in range(n)]
    visit[x][y] = 1
    distance = [[9999]*n for _ in range(n)]
    distance[x][y] = 0
    arr = [x[:] for x in graph]
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] != -1 and visit[nx][ny] == 0:
                visit[nx][ny] = 1
                distance[nx][ny] = distance[x][y] + 1
                Q.append((nx, ny))
    return distance


# Time : 시간, map_customer : 현재 맵에 배치되어있는 사람의 위치와 목적지 위치
Time = 0
map_customer = deque()
while True:
	# 만약 사람이 다 배치되었는데 사람이 다 목적지에 도착하면 탈출
    if len(map_customer) == 0 and len(combini) == 0:
        break

    Time += 1
    # 현재 맵의 사람 수
    LENGO = len(map_customer)
    # 목적지에 도착했을 때 저장 리스트
    remove = []
    for i in range(LENGO):
    	#sx, sy : 현재 사람의 위치, ex, ey : 목적지 위치
        sx, sy, ex, ey = map_customer.popleft()
        GO = go_combini(sx, sy, ex, ey)
        # 이동한 위치
        new_sx, new_sy, DIST = GO.pop()
        # 이동한 위치가 목적지면 해당 위치 -1로 만들기 위해 저장
        if new_sx == ex and new_sy == ey:
            remove.append((ex, ey))
            continue
        # 목적지가 아니면 새로운 위치 저장
        map_customer.append((new_sx, new_sy, ex, ey))
	# 목적지에 도착하면 이동 불가로 만들기
    for i in range(len(remove)):
        x, y = remove.pop()
        graph[x][y] = -1
	# 아직 배치 안된 사람이 있으면 배치
    if len(combini):
        px, py = combini.pop(0)
        now_com = Batch_Basecamp(px, py)
        Px, Py, dist = now_com.pop()
        map_customer.append((Px, Py, px, py))
        graph[Px][Py] = -1

print(Time)