[Python/Codetree] 메이즈 러너

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/submissions?page=1&pageSize=20 

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

문제

M명의 참가자가 미로 탈출하기 게임에 참가하였습니다.

미로의 구성은 다음과 같습니다.

1. 미로는 N×N 크기의 격자입니다. 각 위치는 (r,c)의 형태로 표현되며, 아래로 갈수록 r이 증가, 오른쪽으로 갈수록 c가 증가합니다. 좌상단은 (1,1)입니다.
2. 미로의 각 칸은 다음 3가지 중 하나의 상태를 갖습니다.
   1. 빈 칸
      • 참가자가 이동 가능한 칸입니다.
   2. 벽
      • 참가자가 이동할 수 없는 칸입니다.
      • 1이상 9이하의 내구도를 갖고 있습니다.
      • 회전할 때, 내구도가 1씩 깎입니다.
      • 내구도가 0이 되면, 빈 칸으로 변경됩니다.
   3. 출구
      • 참가자가 해당 칸에 도달하면, 즉시 탈출합니다.

1초마다 모든 참가자는 한 칸씩 움직입니다. 움직이는 조건은 다음과 같습니다.

• 두 위치 (x1,y1), (x2,y2)의 최단거리는 ∣x1−x2∣+∣y1−y2∣로 정의됩니다.
• 모든 참가자는 동시에 움직입니다.
• 상하좌우로 움직일 수 있으며, 벽이 없는 곳으로 이동할 수 있습니다.
• 움직인 칸은 현재 머물러 있던 칸보다 출구까지의 최단 거리가 가까워야 합니다.
• 움직일 수 있는 칸이 2개 이상이라면, 상하로 움직이는 것을 우선시합니다.
• 참가가가 움직일 수 없는 상황이라면, 움직이지 않습니다.
• 한 칸에 2명 이상의 모험가가 있을 수 있습니다.

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

• 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 잡습니다.
• 가장 작은 크기를 갖는 정사각형이 2개 이상이라면, 좌상단 r 좌표가 작은 것이 우선되고, 그래도 같으면 c 좌표가 작은 것이 우선됩니다.
• 선택된 정사각형은 시계방향으로 90도 회전하며, 회전된 벽은 내구도가 1씩 깎입니다.

K초 동안 위의 과정을 계속 반복됩니다. 만약 K초 전에 모든 참가자가 탈출에 성공한다면, 게임이 끝납니다. 게임이 끝났을 때, 모든 참가자들의 이동 거리 합과 출구 좌표를 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 N, M, K가 공백을 사이에 두고 주어집니다.

다음 N개의 줄에 걸쳐서 N×N 크기의 미로에 대한 정보가 주어집니다.

• 0이라면, 빈 칸을 의미합니다.
• 1이상 9이하의 값을 갖는다면, 벽을 의미하며, 해당 값은 내구도를 뜻합니다.

다음 M개의 줄에 걸쳐서 참가자의 좌표가 주어집니다. 모든 참가자는 초기에 빈 칸에만 존재합니다.

다음 줄에 출구의 좌표가 주어집니다. 출구는 빈 칸에만 주어집니다.

• N: 미로의 크기 (4≤N≤10)
• M: 참가자 수 (1≤M≤10)
• K: 게임 시간 (1≤K≤100)

출력 형식

게임 시작 후 K초가 지났거나, 모든 참가자가 미로를 탈출했을 때, 모든 참가자들의 이동 거리 합과 출구 좌표를 출력합니다.

풀이

Code

# 1. 참가자 이동 함수 생성
def move() :
    global ans 

    new_participant = []
    for x, y in participant :
        # 최단 거리 정보 리스트 생성
        distance = []
        # 1-1.
        for dir_x, dir_y in dirs :
            nx, ny = x + dir_x, y + dir_y
            distance.append(abs(exit[0] - nx) + abs(exit[1] - ny))
        # 1-2.
        min_distance = min(distance)
        for dir, d in enumerate(distance) :
            # 현재 거리가 최단 거리일 경우
            if d == min_distance :
                nx, ny = x + dirs[dir][0], y + dirs[dir][1]
                # 다음 위치가 빈 공간일 경우
                if not maze[nx][ny] :
                    # 현재 위치가 출구가 아닐 경우
                    if [nx, ny] != exit :
                        # 새 참가자 리스트에 이동 위치 삽입
                        new_participant.append([nx, ny])
                    # 거리 정보 업데이트
                    ans += 1
                    # for문 탈출
                    break
        # 1-3. 모든 가까운 위치가 벽에 막힌 경우
        else : new_participant.append([x, y])
    # 1-4. 이동한 참가자 리스트 반환
    return new_participant
# 2.가장 작은 정사각형 반환 함수 설정
def check() :
    # 2-1.
    for size in range(2, n) :
        for x1 in range(n - size + 1) :
            for y1 in range(n - size + 1) :
                # 2-1-1. 정사각형의 아래쪽 끝 인덱스 설정
                x2, y2 = x1 + size - 1, y1 + size - 1
                # 2-1-2. 해당 범위 내 출구가 없을 시 스킵
                if not (x1 <= exit[0] <= x2 and y1 <= exit[1] <= y2) : continue
                # 2-1-3.
                for p_x, p_y in participant :
                    if x1 <= p_x <= x2 and y1 <= p_y <= y2 : 
                        return x1, y1, size
# 3. 미로 회전 함수 생성
def rotation() :
    global exit

    new_maze = [line[:] for line in maze]
    # 3-1. 가장 작은 정사각형을 위한 인덱스 추출
    r, c, size = check()
    # 3-2. 참가자 위치 이동 여부 리스트, 출구 이동 여부 리스트 생성
    visited, is_rotated_exit = [False] * len(participant), False
    # 3-3.
    for x1 in range(r, r + size) :
        for y1 in range(c, c + size) :
            # 3-3-1. (x1, y1)을 (0, 0)으로 옮겨주는 작업 수행
            ox, oy = x1 - r, y1 - c
            # 3-3-2. 변환된 위치에서 90도 이동
            rx, ry = oy, size - ox - 1
            # 3-3-3. 다시 x1, y1을 더해줌으로써 변동된 위치에 원래 값 -1 입력
            new_maze[rx + r][ry + c] = maze[x1][y1] - 1 if maze[x1][y1] else maze[x1][y1]
            # 3-3-4. 현재 인덱스에 참가자가 있고 위치 이동이 안 된 경우
            for idx in range(len(participant)) :
                if participant[idx] == [x1, y1] and not visited[idx] :
                    # 방문 처리
                    visited[idx] = True
                    # 위치 이동
                    participant[idx] = [rx + r, ry + c]
            # 3-3-5. 현재 인덱스에 출구가 있는 경우 정보 업데이트
            if [x1, y1] == exit and not is_rotated_exit :
                is_rotated_exit = True
                exit = [rx + r, ry + c]
    # 3-4. 변동된 미로 반환
    return new_maze


n, m, k = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]
participant = [list(map(int, input().split())) for _ in range(m)]
exit = list(map(int, input().split()))

ans = 0
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(m) :
    participant[i][0] -= 1
    participant[i][1] -= 1
exit = [exit[0] - 1, exit[1] - 1]

# 4.
for _ in range(k) :
    # 참가자 이동 함수 실행
    participant = move()
    # 참가자가 모두 탈출한 경우
    if not participant :
        print(f'{ans}\n{exit[0] + 1} {exit[1] + 1}')
        break
    # 미로 회전 함수 실행
    maze = rotation()
# 5. k 초가 지난 경우
else : print(f'{ans}\n{exit[0] + 1} {exit[1] + 1}')