[코드트리] 메이즈 러너 - 파이썬

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/maze-runner/description

import sys
# sys.stdin = open("input.txt", 'r')

def is_board(x, y):
    return 0 <= x < N and 0 <= y < N

def cal_dist(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

# 상 하 좌 우 (문제의 우선순위)
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def move_people(info, key):
    r, c, cnt = info[0][0], info[0][1], info[2]
    cur_dist = cal_dist(r, c, exit[0], exit[1])

    # 상, 하, 좌, 우 우선순위에 따라 한 칸 이동
    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        if not is_board(nr, nc) or board[nr][nc] > 0:
            continue
        
        next_dist = cal_dist(nr, nc, exit[0], exit[1])
        # 현재보다 출구와 가까워지는 경우에만 이동
        if cur_dist > next_dist:
            # 우선순위가 가장 높은 움직임이므로 즉시 이동하고 함수 종료
            people[key][0] = [nr, nc]
            people[key][2] += 1
            if [nr, nc] == exit:
                arrive[key] = 0
                people[key][1] = True
            return

def find_rotate():
    # 가장 작은 정사각형을 찾기 위해 변의 길이(s_len)를 1부터 증가시킴
    for s_len in range(1, N):
        # 정사각형의 좌상단 꼭짓점 (r1, c1)
        for r1 in range(N - s_len):
            for c1 in range(N - s_len):
                r2 = r1 + s_len
                c2 = c1 + s_len
                # 1. 사각형 안에 출구가 있는지 확인
                if not (r1 <= exit[0] <= r2 and c1 <= exit[1] <= c2):
                    continue
                
                is_people_in = False
                # 2. 사각형 안에 참가자가 한 명이라도 있는지 확인
                for [pr, pc], is_arrive, _ in people.values():
                    if is_arrive:
                        continue
                    if r1 <= pr <= r2 and c1 <= pc <= c2:
                        is_people_in = True
                        break
                
                if is_people_in:
                    # 두 조건을 모두 만족하는 가장 작은 사각형을 찾았으므로 즉시 반환
                    return r1, c1, s_len

def rotate_rc(r, c, br, bc, s_len):
    # 1. 좌상단 꼭짓점을 (0,0)으로 이동
    tmp_r, tmp_c = r - br, c - bc
    # 2. 시계방향 90도 회전
    rr = tmp_c
    rc = s_len - tmp_r
    # 3. 원래 위치로 다시 이동
    return rr + br, rc + bc

def rotate(br1, bc1, s_len):
    global board, exit, walls

    br2 = br1 + s_len
    bc2 = bc1 + s_len

    rotated_walls = {}
    new_board = [[0] * N for _ in range(N)]
    
    # 1. 벽 회전 및 내구도 감소
    for key, value in walls.items():
        rc, p = value
        r, c = rc[0], rc[1]
        
        if not (br1 <= r <= br2 and bc1 <= c <= bc2):
            new_wall_board[r][c] = p
            rotated_walls[key] = [rc, p]
        else:
            p -= 1
            if p > 0:
                nr, nc = rotate_rc(r, c, br1, bc1, s_len)
                new_board[nr][nc] = p
                rotated_walls[key] = [[nr, nc], p]
    
    walls = rotated_walls
    board = new_board
    
    # 2. 참가자 회전
    for key, value in people.items():
        rc, is_arrive, _ = value
        if is_arrive:
            continue
        r, c = rc[0], rc[1]
        # ★★★ 오타 수정된 부분 ★★★
        if br1 <= r <= br2 and bc1 <= c <= bc2:
            people[key][0] = rotate_rc(r, c, br1, bc1, s_len)

    # 3. 출구 회전
    exit[0], exit[1] = rotate_rc(exit[0], exit[1], br1, bc1, s_len)

# --- 입력 및 초기 설정 ---
N, M, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
info = [list(map(int, input().split())) for _ in range(M)]
exit_pos = list(map(int, input().split()))
exit = [exit_pos[0] - 1, exit_pos[1] - 1]

walls = {}
tmp = 0
for i in range(N):
    for j in range(N):
        if board[i][j] > 0:
            walls[tmp] = [[i, j], board[i][j]]
            tmp += 1
            
people = {i: [[info[i][0] - 1, info[i][1] - 1], False, 0] for i in range(M)}
arrive = [1] * M

# --- 메인 시뮬레이션 루프 ---
for _ in range(K):
    if sum(arrive) == 0:
        break

    for key, value in people.items():
        if not value[1]:
            move_people(value, key)

    if sum(arrive) == 0:
        break
        
    br, bc, s_len = find_rotate()
    rotate(br, bc, s_len)

# --- 결과 출력 ---
total_dist = sum(p[2] for p in people.values())
print(total_dist)
print(exit[0] + 1, exit[1] + 1)