[코드트리 | 삼성] 메이즈 러너

문제 개요

• 미로
  • M*M 격자 미로
  • 종류
    • 빈칸(참가자 이동 가능)
    • 벽(1-9의 내구도, 회전 시 내구도가 1씩 깎이고 0이 되면 빈칸이 됨)
    • 출구(참가자 도달 시 탈출)
  • 회전
    • 참가자 이동 후 회전
    • 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형
      • 크기가 같다면 좌상단 r좌표가 작은 것, 그 후엔 c좌표가 작은 것이 우선
    • 선택된 정사각형은 시계방향으로 90도 회전, 회전된 벽은 내구도가 1씩 깎임
• 참가자(M명)
  • 상하좌우, 벽이 없는 곳으로 이동
  • 움직인 칸은 현재 칸보다 출구에 가까워야 함
  • 움직일 수 없으면 움직이지 않음
  • 한 칸에 여러 참가자 있을 수 있음
  • 모든 참가자가 동시에 움직임
• 종료조건
  • 모든 참가자가 탈출에 성공했을 때
  • K초가 지났을 때
• 모든 참가자들의 이동 거리 합과 출구 좌표를 출력하기

문제를 위와 같이 정리할 수 있다.

풀이과정, 방향

수행해야 하는 과정은 참가자 이동 >> 회전할 정사각형 선정 >> 미로 회전 >> 게임 종료 조건 확인 순이므로 각각에 대한 함수를 만들어 해결한다.
이번 주 삼성 기출문제를 풀면서 느낀점은

1. 동작을 나누어서 각각에 대한 함수를 만들어서 풀것
2. 어줍잖게 sort같은거 사용해서 편하게 할 생각 말고 조건문으로 하나하나 예외처리 하면서 풀 것

이거 두가지인 것 같다. 그리고 두 명 이상의 참가자가 같은 칸에 있을 수 있고, 각각의 참가자의 위치를 알고 있는 것이 회전할 정사각형을 구하기에 편리하기 때문에 참가자들을 array로 관리하는 것이 편리할 것이다.

유의점

정사각형의 회전 좌표를 어떻게 둘지를 고민하는데 많은 시간이 걸릴 것이다. 전체 사각형이 회전하는 것이 아닌, 일부만을 회전시키는 것이기 때문에 좌표 변환이 헷갈렸는데, 처음부터 좌표를 분해하여 고민했다면 시간이 많이 단축되었을 것 같다.

코드

import copy
n, m, k = map(int, input().split())

maze = []
players = []

for i in range(n):
    arr  = list(map(int,input().split()))
    maze.append(arr)

for i in range(m):
    a,b = map(int, input().split())
    players.append([a-1, b-1])

ey, ex = map(int, input().split())
ey-=1
ex-=1



answer = 0
def player_move():
    global answer
    #플레이어는 벽이 없는 곳으로, 출구까지의 최단 거리가 가까운 곳으로 이동
    #움직일 수 있는 칸이 2개 이상이면, 상하로 움직이는 것이 우선
    left_players = len(players)
    for i in range(left_players):
        py, px = players.pop(0)

        # 출구가 플레이어보다 높은 y값이면 아래로 움직일 수 있나 확인
        if ey > py and maze[py+1][px] == 0:
            answer+=1
            if not(py+1==ey and px==ex):
                players.append([py+1, px])
        # 낮은 y값이면 위로 움직일 수 있나 확인
        elif ey < py and maze[py-1][px] == 0:
            answer+=1
            if not(py-1==ey and px==ex):
                players.append([py-1, px])
        # 높은 x값이면 오른쪽으로 움직일 수 있나 확인
        elif ex > px and maze[py][px+1] == 0:
            answer+=1
            if not(py==ey and px+1==ex):
                players.append([py, px+1])
        # 낮은 x값이면 왼쪽으로 움직일 수 있나 확인
        elif ex < px and maze[py][px-1] == 0:
            answer+=1
            if not(py==ey and px-1==ex):
                players.append([py, px-1])
        # 그 외에는 움직이지 않는다.
        else:
            players.append([py, px])


def find_rectangle():
    global ey, ex
    size = n
    left_y, left_x = 0,0
    for s in range(2, n+1):
        for i in range(n - s+1):
            for j in range(n - s+1):
                if i<= ey < i+s and j<= ex < j+s:
                    for py, px in players:
                        if i<= py < i+s and j<= px < j+s:
                            if s < size:
                                size = s
                                left_y, left_x = i,j
    return [size, left_y, left_x]


def turn_rectangle(size, left_y, left_x, maze):
    # 미로 회전
    new_maze = copy.deepcopy(maze)
    for i in range(size):
        for j in range(size):
            new_i = left_y+j
            new_j = left_x+size-1-i
            new_maze[new_i][new_j] = max(0, maze[left_y+i][left_x+j]-1)
    return new_maze

for i in range(k):
    # print(players)
    player_move()
    # print(players)
    if len(players)==0:
        break
    size, left_y, left_x = find_rectangle()
    maze = turn_rectangle(size, left_y, left_x, maze)
    # 출구 회전
    # print(ey, ex)
    ey, ex = left_y+ex-left_x, left_x+size+left_y-ey-1
    # print(ey, ex)
    # player 회전
    for i in range(len(players)):
        py, px = players[i]
        if left_y<=py<left_y+size and left_x<=px<left_x+size:
            # print(players[i])
            players[i] = [left_y+px-left_x, left_x+size+left_y-py-1]
            # print(players[i])

print(answer)
print(ey+1, ex+1)

느낀점

아까 위에서 정리한 두가지를 명심하면서 풀어야 할 것 같다.

1. 동작을 나누어서 각각에 대한 함수를 만들어서 풀것
2. 어줍잖게 sort같은거 사용해서 편하게 할 생각 말고 조건문으로 하나하나 예외처리 하면서 풀 것