[삼성 SW 역량테스트 기출] 메이즈 러너

import sys

input = sys.stdin.readline

# M명의 참가자가 미로 탈출하기 게임에 참가

# < 미로의 구성 >
# N x N 크기의 격자, 각 칵은 [빈칸 / 벽 / 출구] 로 구성

# 빈칸 : 참가자가 이동 가능한 칸
# 벽 : 참가자가 이동할 수 없는 칸, 1~9 이하의 내구도를 가지고 있음
# 회전할 때 내구도가 1 씩 깎임, 내구도가 0이 되면 빈칸으로 변경
# 출구 : 참가자가 해당 칸에 도착하면 즉시 탈출

# 위 과정을 K초 동안 반복
# 단, K초 전에 모든 참가자가 탈출에 성공한다면 게임이 끝난다.
# 게임이 끝났을 때, [모든 참가자들의 이동 거리의 합]과 [출구 좌표]를 출력

# 두 위치간의 최단거리는 abs(x1-x2) + abs(y1-y2)로 정의
def calculate_dis(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

N, M, K = map(int,input().split())

# 빈칸 : 0, 1~9 : 벽 내구도
area = [list(map(int,input().split())) for _ in range(N)]

dx, dy = [-1,1,0,0], [0,0,-1,1]

answer = 0

INF = float("inf")

# 참가자들의 좌표(모든 참가자는 빈칸에서 시작)
players = []

# 참가자들의 탈출 여부
players_status = [False]*M

for _ in range(M):
    px, py = map(int,input().split())
    players.append([px-1,py-1])

# 출구 좌표(빈칸에만 존재, 참가자와 겹치지 않음)
end_x, end_y = map(int,input().split())
end_x, end_y = end_x - 1, end_y - 1

area[end_x][end_y] = INF

# 종료 조건 : 게임 시작 후 K초가 지났거나, 모든 참가자가 미로를 탈출했을 때
# 출력 : 모든 참가자들의 이동거리의 합 + 출구 좌표

# 부분 90도 회전 + 참가자/출구 좌표 Update 함수
def partial_rotate90(area,x,y,d):

    global end_x, end_y

    temp_area = [arr[:] for arr in area]

    # 단 1번만 회전하기 위한 [이동 여부 저장]용 변수 및 배열
    # (이걸 저장하지 않으면 회전하고 난 뒤 다음 반복문에서 다시 회전할 수 있음)
    # (ex. 0,2 -> 2,2 로 변경된 이후에 2,2 에서 또다시 회전)
    moved_end = False
    moved_players = [False]*M

    for i in range(d):
        for j in range(d):
            # 벽이라면 내구도 -1
            if 1 <= area[x+i][y+j] <= 9:
                temp_area[x+j][y+d-1-i] = area[x+i][y+j]-1
            else:
                temp_area[x+j][y+d-1-i] = area[x+i][y+j]

            # 출구 좌표 Update
            if not moved_end and x+i == end_x and y+j == end_y:
                end_x = x+j
                end_y = y+d-1-i
                moved_end = True

            # 참가자 좌표 Update
            for pi in range(M):
                if not moved_players[pi] and not players_status[pi] and players[pi][0] == x+i and players[pi][1] == y+j:
                    players[pi] = [x+j,y+d-1-i]
                    moved_players[pi] = True

    return temp_area

for main_index in range(K):

    # 1) 참가자의 이동

    # 1초마다 모든 참가자는 한 칸씩 움직인다.
    # 모든 참가자는 동시에 움직인다.
    # 상하좌우로 움직일 수 있으며, [벽이 없는 곳]으로 이동할 수 있다.
    # 움직인 칸은 현재 머물러 있던 칸보다 출구까지의 최단 거리가 가까워야 한다.
    # 움직일 수 있는 칸이 2개 이상이라면, [상하로 움직이는 것]을 우선시 한다 !!
    # 참가자가 움직일 수 없는 상황이라면, 움직이지 않는다.
    # 한 칸에 2명 이상의 참가자가 있을 수 있다.

    # 우선순위 : 거리(-) > 상하 이동

    for i, value in enumerate(players):

        # 이미 탈출한 참가자는 Pass
        if players_status[i]:
            continue

        cx, cy = value[0], value[1]

        # 현재 기준 최단거리
        current_dis = calculate_dis(cx,cy,end_x,end_y)

        # 이동 가능한 좌표 후보
        cases = []
        
        for di in range(4):
            nx, ny = cx + dx[di], cy + dy[di]

            # 영역 밖으로 벗어날 수 없다.
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            
            # 벽으로 이동할 수 없다.
            if 1 <= area[nx][ny] <= 9:
                continue
            
            # 다음 좌표 이동 시 최단거리
            next_dis = calculate_dis(nx,ny,end_x,end_y)
            
            # 움직인 칸은 현재 머물러 있던 칸보다 출구까지의 최단 거리가 가까워야 한다.
            if next_dis >= current_dis:
                continue

            cases.append((next_dis,nx,ny,di))
        
        # 참가자가 움직일 수 없는 상황이라면, 움직이지 않는다.
        if len(cases) == 0:
            continue
        
        # 우선순위 : 거리(-) > 상하 이동
        cases.sort(key = lambda x:(-x[0], -x[3]))

        next_x, next_y = cases[-1][1], cases[-1][2]

        players[i] = [next_x, next_y]
        answer += 1

        # 출구에 도착했을 경우
        if next_x == end_x and next_y == end_y:
            # 탈출 여부 처리
            players_status[i] = True
    
    # 2) 미로의 회전

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

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

    miro_cases = []

    # 모든 좌표에 대하여
    for i in range(N):
        for j in range(N):

            # 1 x 1 부터 N x N 크기까지 완전 탐색
            for length in range(1,N+1):
                ni, nj = i+length, j+length

                # 정사각형 내 좌표 목록
                coors = set()

                # 범위를 넘어가면 Pass
                if ni < 0 or nj < 0 or ni >= N or nj >= N:
                    break

                for x in range(i,ni+1):
                    for y in range(j,nj+1):
                        coors.add((x,y))
                
                # 출구가 없으면 제외
                if (end_x, end_y) not in coors:
                    continue

                have_player = False

                for pi, value in enumerate(players):
                    # 이미 탈출한 참가자는 제외
                    if players_status[pi]:
                        continue
                    
                    if (value[0],value[1]) in coors:
                        have_player = True
                        break
                
                # 참가자가 없으면 제외
                if not have_player:
                    continue

                miro_cases.append((length+1, i,j))
    
    # 단, K초 전에 모든 참가자가 탈출에 성공한다면 게임이 끝난다.
    # (회전할 영역이 없다는 것 == 참가자가 없다는 것 == 모두 탈출했다는 것)
    if len(miro_cases) == 0:
        break

    # 우선순위 : 정사각형 크기(-) > r좌표(-) > c좌표(-)
    miro_cases.sort(key = lambda x:(-x[0], -x[1], -x[2]))

    rect_length, rect_x, rect_y = miro_cases[-1][0], miro_cases[-1][1], miro_cases[-1][2]

    area = partial_rotate90(area,rect_x, rect_y, rect_length)
                
print(answer)
print(end_x+1, end_y+1)

 

이번 문제는 N x N 크기의 격자에서 M명의 참가자가 있다고 할 때, 참가자가 이동하고 미로가 회전하는 것을 K번 반복한 뒤에 [참가자들이 이동한 총 거리]와 [출구의 좌표]를 구하는 문제이다.

 

이전에 풀어본 문제라서 쉽게 풀릴 줄 알았는데, 2차원 배열을 부분 회전하는 코드를 모르고 풀었다가 마지막에 멘붕이 크게 왔다.

 

그래도 덕분에 2차원 배열에서 부분적으로 회전하는 코드를 암기하게 되는 계기가 되었다.

배운 점 및 느낀 점

• 2차원 배열 90/180/270도 회전도 중요하지만, 부분적으로 회전시키는 코드로 알아두자.(N을 다 부분 배열의 크기 d로 바꾸고 좌표에 좌측 상단 좌표인 (x,y)를 다 더해주면 된다.)
• 반복문을 돌면서 좌표를 변경시켜주는 경우에는 해당 좌표가 또다시 변경되지 않도록 '방문 처리'를 반드시 해주도록 하자.