[코드트리] 코드트리 빵 - 파이썬

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/codetree-mon-bread/description

코딩테스트 기출 문제 설명: 코드트리 빵 | 코드트리

---

from collections import deque

# --- 헬퍼 함수 및 전역 변수 ---
def is_range(r, c):
    """격자 범위 안인지 확인"""
    return 0 <= r < n and 0 <= c < n

dr = [-1, 0, 0, 1]
dc = [0, -1, 1, 0]


n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

info = {} 
for idx in range(m):
    r, c = map(int, input().split())
    info[idx + 1] = {'pos': [], 'target': [r - 1, c - 1]}

stores = sorted([[i, j] for i in range(n) for j in range(n) if arr[i][j] == 1])

for r, c in stores:
    arr[r][c] = 0

arrived = {i: False for i in range(1, m + 1)}

# 목표 지점에서부터 갈 수 있는 모든 지점까지의 최단 거리를 담은 배열 생성
def create_distance_map(target_r, target_c):
    dist_map = [[-1]*n for _ in range(n)]
    q = deque([(target_r, target_c, 0)])
    dist_map[target_r][target_c] = 0
    while q:
        r, c, dist = q.popleft()
        for i in range(4):
            nr, nc = r+dr[i], c+dc[i]
            if is_range(nr, nc) and dist_map[nr][nc] == -1 and arr[nr][nc] != -1:
                dist_map[nr][nc]  = dist + 1
                q.append((nr, nc, dist+1))
    return dist_map

def move(man_id, dist_map):
    cur_r, cur_c = info[man_id]['pos']
    min_dist = float('inf')
    best_direc = -1

    for d in range(4):
        nr, nc = cur_r+dr[d], cur_c+dc[d]
        if is_range(nr, nc) and dist_map[nr][nc] != -1:
            if dist_map[nr][nc] <min_dist:
                min_dist = dist_map[nr][nc]
                best_direc = d
    if best_direc != -1:
        next_r, next_c = cur_r+dr[best_direc], cur_c+dc[best_direc]
        info[man_id]['pos'] = [next_r, next_c]


def find_base_camp(target_r, target_c):
    dist_map = create_distance_map(target_r, target_c)
    min_dist = float('inf')
    best_basecamp = [-1, -1]
    for r,c in stores:
        dist = dist_map[r][c]
        if dist != -1 and dist<min_dist:
            min_dist = dist
            best_basecamp = [r,c]
    arr[best_basecamp[0]][best_basecamp[1]] = -1
    stores.remove(best_basecamp)
    return best_basecamp

# 메인 시뮬레이션
t = 0
while True:
    t += 1
    for man_id in range(1,m+1):
        if info[man_id]['pos'] and not arrived[man_id]:
            target_r, target_c = info[man_id]['target']
            dist_map = create_distance_map(target_r, target_c)
            move(man_id, dist_map)

    # 편의점 도착 처리
    for man_id in range(1, m+1):
        if info[man_id]['pos'] and not arrived[man_id]:
            if info[man_id]['pos'] == info[man_id]['target']:
                arrived[man_id] = True
                r, c = info[man_id]['pos']
                arr[r][c] = -1

    # t 번 사람 베이스캠프에 입장
    if t<=m:
        target_r, target_c = info[t]['target']
        base_r, base_c = find_base_camp(target_r, target_c)
        info[t]['pos'] = [base_r, base_c]
    # 4단계: 종료 조건 확인
    if all(arrived.values()):
        break

print(t)