코드트리 - 마법의 숲 탐색 (Python)

import sys
from collections import deque

# Solution
class Golem:
    def __init__(self, id, x, y, d):
        self.id = id
        self.x = x
        self.y = y
        self.d = d

    def get_exit(self):
        dir = dirs[self.d]
        return self.x + dir[0], self.y + dir[1]

    def __repr__(self):
        return f"{self.id}"

# Step 1: 골렘 이동
# Step 1-1: 남쪽 이동
def move_south(golem):
    south_dirs = [(1, -1), (2, 0), (1, 1)]
    is_success = can_move(golem.x, golem.y, south_dirs)

    if is_success:
        golem.x += 1

    return is_success

# Step 1-2: 서쪽 이동
def move_west(golem):
    x, y, d = golem.x, golem.y, golem.d

    is_success = rotate_west(golem)

    if is_success:
        is_success = move_south(golem)

    if not is_success:
        golem.x = x
        golem.y = y
        golem.d = d

    return is_success

# 서쪽 회전
def rotate_west(golem):
    west_dirs = [(-1, -1), (0, -2), (1, -1)]
    is_success = can_move(golem.x, golem.y, west_dirs)

    if is_success:
        golem.y -= 1
        golem.d = (golem.d - 1) % 4

    return is_success

# Step 1-3: 동쪽 이동
def move_east(golem):
    x, y, d = golem.x, golem.y, golem.d

    is_success = rotate_east(golem)

    if is_success:
        is_success = move_south(golem)

    if not is_success:
        golem.x = x
        golem.y = y
        golem.d = d

    return is_success

# 동쪽 회전
def rotate_east(golem):
    east_dirs = [(-1, 1), (0, 2), (1, 1)]
    is_success = can_move(golem.x, golem.y, east_dirs)

    if is_success:
        golem.y += 1
        golem.d = (golem.d + 1) % 4

    return is_success

# Step 1-4: map에 기록
def stop(golem):
    # 이동 실패
    if golem.x < 1:
        return False

    maps[golem.x][golem.y] = golem.id
    for dx, dy in dirs:
        nx, ny = golem.x + dx, golem.y + dy
        maps[nx][ny] = golem.id

    return True

# 이동 가능 여부 판단
def can_move(x, y, move_dirs):
    for dx, dy in move_dirs:
        nx, ny = x + dx, y + dy

        if not in_range(nx, ny) or (nx >= 0 and maps[nx][ny] > 0):
            return False

    return True

# Step 2: 정령 이동
def move_fairy(r, c):
    row = 0
    visited = [[False] * C for _ in range(R)]
    dq = deque()
    dq.append([r, c, maps[r][c]])
    visited[r][c] = True

    while dq:
        x, y, g_id = dq.popleft()

        row = max(row, x)

        for dx, dy in dirs:
            nx, ny = x + dx, y + dy

            if nx >= 0 and in_range(nx, ny) and maps[nx][ny] > 0 and not visited[nx][ny]:
                if maps[nx][ny] == g_id:
                    dq.append([nx, ny, g_id])
                    visited[nx][ny] = True

                else:
                    golem = golem_dict[g_id]
                    exit_x, exit_y = golem.get_exit()
                    if exit_x == x and exit_y == y:
                        dq.append([nx, ny, maps[nx][ny]])
                        visited[nx][ny] = True

    return row + 1

def in_range(x, y):
    return x < R and 0 <= y < C

# Main
R, C, K = map(int, sys.stdin.readline().split())
golem_dict = {}
golem_list = []
maps = [[0] * C for _ in range(R)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # 북 동 남 서
total_row = 0

# get golem
for i in range(1, K + 1):
    c, d = map(int, sys.stdin.readline().split())
    golem = Golem(i, -2, c - 1, d)
    golem_list.append(golem)
    golem_dict[i] = golem

# game
for golem in golem_list:
    is_success = True

    while is_success:
        is_success = move_south(golem)

        if not is_success:
            is_success = move_west(golem)

        if not is_success:
            is_success = move_east(golem)

        if not is_success:
            is_success = stop(golem)

            # map overflow => reset map (정령 이동 x)
            if not is_success:
                maps = [[0] * C for _ in range(R)]

            if is_success:
                max_row = move_fairy(golem.x, golem.y)
                total_row += max_row
            break

print(total_row)