메이즈 러너

코테는 진짜 운빨도 중요한 듯...

상반기 오전 문제는 진짜 더러워도 너무 더러웠다... 구현 난이도가 빡세진 않은데 온갖 걸 섞어 논 잡탕 느낌이었고, 엣지관리도 어려워서 골드1 이였던 반면 상반기 오후 문제는 엣지 관리가 훨씬 쉬웠던 듯... 하... 진짜ㅠㅠㅠ

1. 실패 -> 모두 탈출할 경우 return 값이 없어서 NoneType 오류 발생.

n, m, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
participant_infos = [list(map(int, input().split())) for _ in range(m)]
participant_infos = list(map(lambda x: [x[0] - 1, x[1] - 1], participant_infos))
participant_graphs = [[[] for _ in range(n)] for _ in range(n)]
exit_info = list(map(int, input().split()))
exit_info = list(map(lambda x: x - 1, exit_info))
participant_graphs[exit_info[0]][exit_info[1]] = 2
total_move = 0


def visit_check():
    global participant_infos, participant_graphs, exit_info
    g_y, g_x = exit_info[0], exit_info[1]
    participant_graphs = [[[] for _ in range(n)] for _ in range(n)]
    participant_graphs[g_y][g_x] = 2
    for y, x in participant_infos:
        participant_graphs[y][x].append(1)  # 방문체크


def validation(ny, nx):
    global n
    return 0 <= ny < n and 0 <= nx < n


def participant_move(y, x):
    global exit_info, graph, participant_graphs, total_move
    g_y, g_x = exit_info[0], exit_info[1]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if validation(ny, nx) and graph[ny][nx] == 0:
            if abs(g_y - ny) + abs(g_x - nx) == 0:  # 목표 지점에 도달, 탈출
                total_move += len(participant_graphs[y][x])
                participant_graphs[y][x] = []
                return y, x
            if abs(g_y - y) + abs(g_x - x) > abs(g_y - ny) + abs(g_x - nx):
                return ny, nx
    return y, x


def participants_move():
    global n, graph, participant_graphs, total_move, exit_info
    g_y, g_x = exit_info[0], exit_info[1]
    tmp_participant_graph = [[[] for _ in range(n)] for _ in range(n)]
    tmp_participant_graph[g_y][g_x] = 2

    for y in range(n):
        for x in range(n):
            if participant_graphs[y][x] != [] and participant_graphs[y][x] != 2:
                ny, nx = participant_move(y, x)
                if (ny, nx) != (y, x):
                    total_move += len(participant_graphs[y][x])
                tmp_participant_graph[ny][nx].extend(participant_graphs[y][x])
    participant_graphs = tmp_participant_graph  # 그래프 동기화


def section(size, g_y, g_x):
    global participant_graphs
    for y in range(g_y - size, g_y + 1):
        for x in range(g_x - size, g_x + 1):
            if participant_graphs[y][x] != [] and participant_graphs[y][x] != 2:
                return True
    return False

def find_rectangle():
    global exit_info, participant_graphs, n
    g_y = exit_info[0]
    g_x = exit_info[1]
    size = 1
    while True:
        size += 1
        for y in range(n):
            for x in range(n):
                g_flag = False
                p_flag = False
                try:
                    for ny in range(y, y + size):
                        for nx in range(x, x + size):
                            if participant_graphs[ny][nx] == 2:
                                g_flag = True
                            elif participant_graphs[ny][nx] != []:
                                p_flag = True
                    if g_flag and p_flag:
                        return y, x, size
                except:
                    pass
        if size ==4 :
            break

def trans_rectangle(ty, tx, size):
    global graph, participant_graphs, exit_info
    g_y, g_x = exit_info[0], exit_info[1]
    tmp_graph = []
    tmp_participant_graphs = []
    for y in range(ty, ty + size):
        peice_tmp_graph = []
        peice_tmp_participant_graphs = []
        for x in range(tx, tx + size):
            peice_tmp_graph.append(graph[y][x])
            peice_tmp_participant_graphs.append(participant_graphs[y][x])
        tmp_graph.append(peice_tmp_graph)
        tmp_participant_graphs.append(peice_tmp_participant_graphs)

    tmp_graph = list(map(list, zip(*tmp_graph)))
    tmp_graph = list(map(lambda x: list(reversed(x)), tmp_graph))

    tmp_participant_graphs = list(map(list, zip(*tmp_participant_graphs)))
    tmp_participant_graphs = list(map(lambda x: list(reversed(x)), tmp_participant_graphs))

    for y in range(ty, ty + size):
        for x in range(tx, tx + size):
            graph[y][x] = tmp_graph[y - ty][x - tx]
            if graph[y][x] >= 1:
                graph[y][x] -= 1
            participant_graphs[y][x] = tmp_participant_graphs[y - ty][x - tx]
    return


def refind_exit_participants():
    global exit_info, participant_infos, participant_graphs, n
    participant_infos = []  # 초기화
    for y in range(n):
        for x in range(n):
            if participant_graphs[y][x] == 2:
                exit_info = [y, x]
            elif participant_graphs[y][x] != []:
                for _ in range(len(participant_graphs[y][x])):
                    participant_infos.append([y, x])

for _ in range(k):

    visit_check()
    participants_move()
    ty, tx, size = find_rectangle()
    trans_rectangle(ty, tx, size)
    refind_exit_participants()
print(total_move)
print(exit_info[0] + 1, exit_info[1] + 1)
# 좌상단 1,1

# 빈 칸
# 참가자가 이동 가능한 칸입니다.

# 벽
# 참가자가 이동할 수 없는 칸입니다.
# 1이상 9이하의 내구도를 갖고 있습니다.
# 회전할 때, 내구도가 1씩 깎입니다.
# 내구도가 0이 되면, 빈 칸으로 변경됩니다.

# 출구
# 참가자가 해당 칸에 도달하면, 즉시 탈출합니다.

# 모든 참가자가 이동을 끝냈으면, 다음 조건에 의해 미로가 회전합니다.


# 모든 참가자들의 이동 거리 합과 출구 좌표를 출력

 

2. 성공

n, m, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
participant_infos = [list(map(int, input().split())) for _ in range(m)]
participant_infos = list(map(lambda x: [x[0] - 1, x[1] - 1], participant_infos))
participant_graphs = [[[] for _ in range(n)] for _ in range(n)]
exit_info = list(map(int, input().split()))
exit_info = list(map(lambda x: x - 1, exit_info))
participant_graphs[exit_info[0]][exit_info[1]] = 2
total_move = 0


def visit_check():
    global participant_infos, participant_graphs, exit_info
    g_y, g_x = exit_info[0], exit_info[1]
    participant_graphs = [[[] for _ in range(n)] for _ in range(n)]
    participant_graphs[g_y][g_x] = 2
    for y, x in participant_infos:
        participant_graphs[y][x].append(1)  # 방문체크


def validation(ny, nx):
    global n
    return 0 <= ny < n and 0 <= nx < n


def participant_move(y, x):
    global exit_info, graph, participant_graphs, total_move
    g_y, g_x = exit_info[0], exit_info[1]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if validation(ny, nx) and graph[ny][nx] == 0:
            if abs(g_y - ny) + abs(g_x - nx) == 0:  # 목표 지점에 도달, 탈출
                total_move += len(participant_graphs[y][x])
                participant_graphs[y][x] = []
                return y, x
            if abs(g_y - y) + abs(g_x - x) > abs(g_y - ny) + abs(g_x - nx):
                return ny, nx
    return y, x


def participants_move():
    global n, graph, participant_graphs, total_move, exit_info
    g_y, g_x = exit_info[0], exit_info[1]
    tmp_participant_graph = [[[] for _ in range(n)] for _ in range(n)]
    tmp_participant_graph[g_y][g_x] = 2

    for y in range(n):
        for x in range(n):
            if participant_graphs[y][x] != [] and participant_graphs[y][x] != 2:
                ny, nx = participant_move(y, x)
                if (ny, nx) != (y, x):
                    total_move += len(participant_graphs[y][x])
                tmp_participant_graph[ny][nx].extend(participant_graphs[y][x])
    participant_graphs = tmp_participant_graph  # 그래프 동기화


def section(size, g_y, g_x):
    global participant_graphs
    for y in range(g_y - size, g_y + 1):
        for x in range(g_x - size, g_x + 1):
            if participant_graphs[y][x] != [] and participant_graphs[y][x] != 2:
                return True
    return False

def find_rectangle():
    global exit_info, participant_graphs, n
    size = 0
    while True:
        size += 1
        for y in range(n):
            for x in range(n):
                g_flag = False
                p_flag = False
                try:
                    for ny in range(y, y + size):
                        for nx in range(x, x + size):
                            if participant_graphs[ny][nx] == 2:
                                g_flag = True
                            elif participant_graphs[ny][nx] != []:
                                p_flag = True
                    if g_flag and p_flag:
                        return y, x, size
                except:
                    pass
        if size >= n:
            return
def trans_rectangle(ty, tx, size):
    global graph, participant_graphs, exit_info
    g_y, g_x = exit_info[0], exit_info[1]
    tmp_graph = []
    tmp_participant_graphs = []
    for y in range(ty, ty + size):
        peice_tmp_graph = []
        peice_tmp_participant_graphs = []
        for x in range(tx, tx + size):
            peice_tmp_graph.append(graph[y][x])
            peice_tmp_participant_graphs.append(participant_graphs[y][x])
        tmp_graph.append(peice_tmp_graph)
        tmp_participant_graphs.append(peice_tmp_participant_graphs)

    tmp_graph = list(map(list, zip(*tmp_graph)))
    tmp_graph = list(map(lambda x: list(reversed(x)), tmp_graph))

    tmp_participant_graphs = list(map(list, zip(*tmp_participant_graphs)))
    tmp_participant_graphs = list(map(lambda x: list(reversed(x)), tmp_participant_graphs))

    for y in range(ty, ty + size):
        for x in range(tx, tx + size):
            graph[y][x] = tmp_graph[y - ty][x - tx]
            if graph[y][x] >= 1:
                graph[y][x] -= 1
            participant_graphs[y][x] = tmp_participant_graphs[y - ty][x - tx]
    return


def refind_exit_participants():
    global exit_info, participant_infos, participant_graphs, n
    participant_infos = []  # 초기화
    for y in range(n):
        for x in range(n):
            if participant_graphs[y][x] == 2:
                exit_info = [y, x]
            elif participant_graphs[y][x] != []:
                for _ in range(len(participant_graphs[y][x])):
                    participant_infos.append([y, x])

for _ in range(k):

    visit_check()
    participants_move()
    try:
        ty, tx, size = find_rectangle()
    except:
        break
    trans_rectangle(ty, tx, size)
    refind_exit_participants()
print(total_move)
print(exit_info[0] + 1, exit_info[1] + 1)
# 좌상단 1,1

# 빈 칸
# 참가자가 이동 가능한 칸입니다.

# 벽
# 참가자가 이동할 수 없는 칸입니다.
# 1이상 9이하의 내구도를 갖고 있습니다.
# 회전할 때, 내구도가 1씩 깎입니다.
# 내구도가 0이 되면, 빈 칸으로 변경됩니다.

# 출구
# 참가자가 해당 칸에 도달하면, 즉시 탈출합니다.

# 모든 참가자가 이동을 끝냈으면, 다음 조건에 의해 미로가 회전합니다.


# 모든 참가자들의 이동 거리 합과 출구 좌표를 출력