[코드트리] 메이즈 러너 / Python(파이썬)

문제

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/description?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초가 지났거나, 모든 참가자가 미로를 탈출했을 때, 모든 참가자들의 이동 거리 합과 출구 좌표를 출력합니다.

풀이

아이디어

핵심으로 풀어야할 부분은 회전하는 박스를 찾는 것, 박스 안을 시계방향으로 회전하는 것이다.

해야 할 일은 다음과 같다

1. 맵 구성
2. 사람 이동
3. 회전

맵 구성

필요한 자료구조를 정리해 보자.

1. 벽의 정보를 저장 : dict
2. 사람의 현재좌표, 탈출여부, 이동거리 저장 : dict
3. 출구 좌표 저장 : list
4. 도착확인 리스트 : list
5. 벽 격자 저장 : list

입력 좌표가 1부터 시작하기 때문에 헷갈리지 않게 인덱스를 조정하여 저장한다.

# 맵구성
N, M, K = map(int, input().split())
wall_board = [list(map(int, input().split())) for _ in range(N)]
info = [list(map(int, input().split())) for _ in range(M)]
# 벽 정보 : [좌표, 내구도]
wall = [0 for i in range(N) for j in range(N) if wall_board[i][j] > 0]
walls = {i: [[],[]]for i in range(len(wall))}
temp = 0
for i in range(N):
    for j in range(N):
        if wall_board[i][j] > 0:
            walls[temp][0] = [i, j]
            walls[temp][1] = wall_board[i][j]
            temp +=1
            
# 사람 번호 : [현재좌표, 탈출여부, 이동거리]
people = {i :[[info[i][0]-1, info[i][1]-1], False, 0] for i in range(M)}
exit = list(map(int, input().split()))  # 출구 좌표
exit[0], exit[1] = exit[0]-1, exit[1]-1

arrive = [1]*M      # 도착 정보 (도착 : 0, not yet : 1)

사람 이동

이동가능한 경우 중, 출구가 가까워지는 방향을 선택한다.

가까워지지 않으면 이동하지 않으며, 방향 우선순위는 상하>좌우 이다.

출력은 이동거리를 구해야하므로 이동거리도 저장한다.

• 이동가능한 경우
  • 상하 > 좌우
  • 이동거리 +1
  • 이동 후, 탈출
• 이동 불가능 한 경우 : 이동x

def move_people(info, key):
    x, y, cnt = info[0][0], info[0][1], info[2]
    cur_dist = cal_dist(x, y, exit[0], exit[1])
    candi = []

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        # 격자 밖인 경우 / 벽인 경우
        if not is_board(nx, ny) or wall_board[nx][ny] > 0:
            continue
        next_dist = cal_dist(nx, ny, exit[0], exit[1])
        # 거리가 가까워 지면 이동
        if cur_dist > next_dist:
            cur_dist = next_dist
            candi.append([nx, ny])
        # 움직일 수 없음
    if len(candi) == 0:
        return
    nx, ny = candi.pop()
    # 탈출한 경우 -> 탈출리스트 추가, 탈출 flag on
    if [nx, ny] == exit:
        arrive[key] = 0
        people[key][1] = True

    people[key][0] = [nx, ny]
    people[key][2] += 1

    return

회전

1. 회전 박스 찾기

최소 1명이상의 사람을 포함하고, 출구를 감싸는 박스를 찾아야 한다.

박스가 여러개인 경우, [행이 작은 것 > 열이 작은 것] 우선순위를 가진다.

어떻게 찾을지 꽤나 고민을 했다.

결론은 완전탐색으로 하나하나 늘려가면서 찾는 방법.

(0, 0)이 꼭짓점이며, 길이가 1인 정사각형을 한칸한칸 옮기면서 사람/출구를 포함하는지 확인한다.

이렇게 이동하면 박스의 우선순위도 지켜가며 찾을 수 있음.

길이는 1부터 n까지 늘려가면서 확인한다.

사람은 1명이상만 있으면 되기 때문에 flag를 이용하여 확인

def find_rotate():
    # 변의 길이
    for ll in range(1, N+1):
        for x1 in range(0, N-ll +1):
            for y1 in range(0, N-ll+1):
                x2 = x1 + ll
                y2 = y1 + ll
                # 사각형 안에 출구가 없음 -> continue
                if not (x1<= exit[0] <= x2 and y1 <= exit[1] <= y2):
                    continue

                is_people = False
                # 사각형안에 사람이 있는지 확인
                for [px, py], is_arrive, _ in people.values():
                    if is_arrive:continue
                    if x1<= px <= x2 and y1<= py <= y2:
                        is_people = True
                        break
                if is_people:
                    return x1, y1, x2, y2, ll

1. 회전하기

이때까지 회전은 격자단위를 전체 회전했다.

이번에는 정해진 박스 안에서만 시계방향을 회전시켜야 하기 때문에 고민이 많이 필요했다.

회전하는 것은 어렵지 않았지만 좌표가 자꾸 틀어져서 고민..

결국은 퍼즐조각채우기와 같은 방법을 쓰는게 포인트인 것같다.

회전 박스를 잘라내서 (0,0)으로 조정하고, 회전 시킨 후, 다시 붙여넣기 하는 방법.

분명 다 잘 했는데 또 테케 2번에서 걸렸다.

항상 테케를 한번에 넘어가는 법이 없어서 속상하다 ㅠㅠ

이유는 1. 사람이동 단계가 끝난 후, 모두 탈출하면 끝내야 하는데 그렇지 않았기 때문..

막히면 조건을 다시 하나하나 검토하는 것이 쓸데없는 디버깅을 줄일 수 있을 것이다..

def rotate_xy(x, y, bx, by, s_len):
    tempx, tempy = x - bx, y - by
    rx = tempy
    ry = s_len - tempx
    return rx+bx, ry+by

def rotate(bx1, by1, bx2, by2, s_len):
    # 사각형 안의 벽 내구도 -1
    for idx in range(len(walls)):
        x, y = walls[idx][0][0], walls[idx][0][1]
        if bx1<= x <= bx2 and by1 <= y <= by2 and walls[idx][1] >= 0:
            walls[idx][1] = walls[idx][1]-1

    for id,[xy, is_arrive, _] in enumerate(people.values()):
        # 이미 탈출한 사람 이동x
        if is_arrive:
           continue
        x, y = xy[0], xy[1]
        if bx1<= x <= bx2 and by1 <= y <= by2:
            people[id][0] = rotate_xy(x,y, bx1, by1, s_len)

    wall_board = [[0]*N for _ in range(N)]
    # 벽 회전
    for id, [xy, p] in enumerate(walls.values()):
        x, y = xy[0], xy[1]
        # 내구도가 사라진 벽 처리
        if p <= 0: continue

        if bx1 <= x <= bx2 and by1 <= y <= by2:
            nx, ny = rotate_xy(x, y, bx1, by1, s_len)
            walls[id][0] = [nx, ny]
            wall_board[nx][ny] = walls[id][1]

        else:
            wall_board[x][y] = walls[id][1]

    # 출구 회전
    exit[0], exit[1] = rotate_xy(exit[0], exit[1], bx1, by1, s_len)

    return wall_board

코드

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


# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = 100000000000


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

def move_people(info, key):
    x, y, cnt = info[0][0], info[0][1], info[2]
    cur_dist = cal_dist(x, y, exit[0], exit[1])
    candi = []

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        # 격자 밖인 경우 / 벽인 경우
        if not is_board(nx, ny) or wall_board[nx][ny] > 0:
            continue
        next_dist = cal_dist(nx, ny, exit[0], exit[1])
        # 거리가 가까워 지면 이동
        if cur_dist > next_dist:
            cur_dist = next_dist
            candi.append([nx, ny])
        # 움직일 수 없음
    if len(candi) == 0:
        return
    nx, ny = candi.pop()
    # 탈출한 경우 -> 탈출리스트 추가, 탈출 flag on
    if [nx, ny] == exit:
        arrive[key] = 0
        people[key][1] = True

    people[key][0] = [nx, ny]
    people[key][2] += 1

    return

def find_rotate():
    # 변의 길이
    for ll in range(1, N+1):
        for x1 in range(0, N-ll +1):
            for y1 in range(0, N-ll+1):
                x2 = x1 + ll
                y2 = y1 + ll
                # 사각형 안에 출구가 없음 -> continue
                if not (x1<= exit[0] <= x2 and y1 <= exit[1] <= y2):
                    continue

                is_people = False
                # 사각형안에 사람이 있는지 확인
                for [px, py], is_arrive, _ in people.values():
                    if is_arrive:continue
                    if x1<= px <= x2 and y1<= py <= y2:
                        is_people = True
                        break
                if is_people:
                    return x1, y1, x2, y2, ll

def rotate_xy(x, y, bx, by, s_len):
    tempx, tempy = x - bx, y - by
    rx = tempy
    ry = s_len - tempx
    return rx+bx, ry+by

def rotate(bx1, by1, bx2, by2, s_len):
    # 사각형 안의 벽 내구도 -1
    for idx in range(len(walls)):
        x, y = walls[idx][0][0], walls[idx][0][1]
        if bx1<= x <= bx2 and by1 <= y <= by2 and walls[idx][1] >= 0:
            walls[idx][1] = walls[idx][1]-1

    for id,[xy, is_arrive, _] in enumerate(people.values()):
        # 이미 탈출한 사람 이동x
        if is_arrive:
           continue
        x, y = xy[0], xy[1]
        if bx1<= x <= bx2 and by1 <= y <= by2:
            people[id][0] = rotate_xy(x,y, bx1, by1, s_len)

    wall_board = [[0]*N for _ in range(N)]
    # 벽 회전
    for id, [xy, p] in enumerate(walls.values()):
        x, y = xy[0], xy[1]
        # 내구도가 사라진 벽 처리
        if p <= 0: continue

        if bx1 <= x <= bx2 and by1 <= y <= by2:
            nx, ny = rotate_xy(x, y, bx1, by1, s_len)
            walls[id][0] = [nx, ny]
            wall_board[nx][ny] = walls[id][1]

        else:
            wall_board[x][y] = walls[id][1]

    # 출구 회전
    exit[0], exit[1] = rotate_xy(exit[0], exit[1], bx1, by1, s_len)

    return wall_board

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

# 맵구성
N, M, K = map(int, input().split())
wall_board = [list(map(int, input().split())) for _ in range(N)]
info = [list(map(int, input().split())) for _ in range(M)]
# 벽 정보 : [좌표, 내구도]
wall = [0 for i in range(N) for j in range(N) if wall_board[i][j] > 0]
walls = {i: [[],[]]for i in range(len(wall))}
temp = 0
for i in range(N):
    for j in range(N):
        if wall_board[i][j] > 0:
            walls[temp][0] = [i, j]
            walls[temp][1] = wall_board[i][j]
            temp +=1
# 사람 번호 : [현재좌표, 탈출여부, 이동거리]
people = {i :[[info[i][0]-1, info[i][1]-1], False, 0] for i in range(M)}
exit = list(map(int, input().split()))  # 출구 좌표
exit[0], exit[1] = exit[0]-1, exit[1]-1

arrive = [1]*M      # 도착 정보 (도착 : 0, not yet : 1)

# 0. 모두 탈출 했으면 끝
for k in range(K):
    if sum(arrive) == 0:
        break
    # 1. 이동
    for key in people.keys():
        # 이미 탈출한 경우
        if people[key][1]:
            continue
        move_people(people[key], key)

    # 1.1 이동 후, 모두 탈출 한 경우
    if sum(arrive) == 0:
        break

    # 2. 회전 박스 찾기
    bx1, by1, bx2, by2, s_len = find_rotate()

    # 3. 회전
    wall_board = rotate(bx1, by1, bx2, by2,s_len)

cnt = [people[i][2] for i in range(M)]
print(sum(cnt))

print(exit[0]+1, exit[1]+1)