🔴 문제 개요
이 문제는 코드트리의 일반 연습/기출 문제에 수록되어 있는 메이즈 러너 문제입니다. 특히 23년도 상반기 삼성 SW 역량 테스트 기출 문제로도 잘 알려져 있는 문제입니다.
제한 사항
- 미로의 크기 : 4 <= N <= 10
- 참가자 수 : 1 <= M <= 10
- 게임 시간 : 1 <= K <= 100
문제 유형
- 문제의 설명과, 제한 사항의 조건으로 미루어보아 본 문제의 유형은 시뮬레이션으로 판단할 수 있습니다.
🟡 Solution
문제에서 구현해야 할 부분은 크게 3가지입니다.
1. 참가자들을 모두 이동시키기
2. 출구(E)와 최소 한 명의 참가자를 포함하는 최소 넓이 직사각형 구하기
3. 최소 넓이 직사각형을 회전시키기
우선, 문제의 input을 받는 부분과 위 구현의 추상 메서드, output 출력부를 정의해보겠습니다.
input, 추상 메서드, output 정의
import sys
from typing import Tuple
from collections import deque
input = sys.stdin.readline
N, M, K = map(int, input().rstrip().split())
matrix = [list(map(int, input().rstrip().split())) for _ in range(N)]
participants = deque(
[tuple(map(lambda x: int(x) - 1, input().rstrip().split())) for _ in range(M)]
)
E = tuple(map(lambda x: int(x) - 1, input().rstrip().split()))
answer = 0
def move(py: int, px: int) -> int:
pass
def get_rectangle() -> Tuple[int, int, int, int]
pass
def rotate(min_y: int, min_x: int, max_y: int, max_x: int) -> None:
pass
# 최대 k초 이동 가능
for i in range(K):
# 참가자 당 한 번씩 move
M = len(participants)
for _ in range(M):
answer += move(*participants.popleft())
# 이동 과정에서 참가자가 모두 탈출한 경우 종료
if not participants:
break
# 정사각형 좌표를 구해 해당 위치 90도 rotate
rotate(*get_rectangle())
print(answer)
print(E[0] + 1, E[1] + 1)- 문제에서 수의 범위는 1부터 시작하므로, 0에서 시작하는 인덱스에 맞춰 -1 하여 모든 수를 받아줍니다.
- 참가자 리스트(
participants)를 deque으로 받아서 큐로 활용합니다. - 하단의 메인부에서는 최대 K번 반복하는 반복문을 정의합니다.
participants에서 모든 participant를 한 번씩 pop하여 이동 시킵니다.- 만약 이동과정에서 참가자가 모두 탈출한 경우 종료합니다.
- 이동 후, 출구의 좌표(
E)와participants의 좌표를 고려하여 정사각형 좌표를 구해 해당 위치를 90도 회전시킵니다.
- 최종 이동 횟수(
answer)와 최종E를 반환합니다.
먼저 참가자를 어떻게 이동시킬지 생각해보겠습니다.
move()
dy = [-1, 1, 0, 0] # 상 하 좌 우 순서
dx = [0, 0, -1, 1]
def move(py: int, px: int) -> int:
"""
특정 참가자를 출구와 가까운 쪽으로 1만큼 이동시킨다.
이동 시 출구와 가까워지는 쪽으로, 상-하-좌-우 우선순위로 이동한다.
input : 이동시킬 참가자 (y, x) 좌표
output : 참가자 이동 여부 (이동했으면 1, 이동하지 않았으면 0)
"""
# 기존 참가자와 출구까지의 최단 거리
dist = abs(py - E[0]) + abs(px - E[1])
for d in range(4):
ny = py + dy[d]
nx = px + dx[d]
# 이동 후 참가자와 출구까지의 최단 거리
new_dist = abs(ny - E[0]) + abs(nx - E[1])
# 이동 가능하며, 출구와 가까워지는 경우
if 0 <= ny < N and 0 <= nx < N and matrix[ny][nx] == 0 and new_dist < dist:
# 이동 후 좌표가 탈출구인 경우 탈출시키고 아닌 경우, 이동시킨 좌표를 큐에 삽입
if (ny, nx) != E:
participants.append((ny, nx))
# 이동 성공 시 count 1 반환
return 1
# 이동 실패 시 원래 좌표를 다시 큐에 삽입, count 0 반환
participants.append((py, px))
return 0- 주의해야 할 점은 출구와 가까워지는 쪽으로 1회 이동 가능한 점입니다.
- 우리가 고려할 수 있는 방향은 상, 하, 좌, 우 인데, 이 네 방향 중 출구와 가까워지는 방향은 한 방향밖에 존재하지 않습니다.
- 따라서 상 하 좌 우 중 먼저 이동 가능한 좌표가 나오면, 큐에 좌표를 업데이트 하고, 다른 방향은 고려하지 않고 반복문을 탈출해야 합니다.
- 이 때, 이동 후 좌표가
E인 경우는 다시 큐에 넣으면 안되겠죠.
- 상, 하, 좌, 우 중 출구와 가까워지는 방향으로 이동할 수 없을 경우 원래 좌표를 다시
participants에 삽입하고 0을 반환합니다. - 이동 성공시는 1을 반환 하여 함수 바깥 answer에 더해줄 수 있도록 합니다.
모든 참가자 이동이 끝났으면, E와 participants 를 바탕으로 회전시킬 정사각형의 좌표를 구해야합니다.
get_rectangle()
def get_rectangle() -> Tuple[int, int, int, int]:
"""
출구와 최소 한 명의 참가자를 포함하는 최소 넓이 직사각형의 네 좌표를 반환한다.
input : x
output : 직사각형의 min_y, min_x, max_y, max_x
"""
rectangles = []
for y, x in set(participants):
max_y = max(y, E[0])
min_y = min(y, E[0])
max_x = max(x, E[1])
min_x = min(x, E[1])
# 한 변의 길이
side_len = max(max_y - min_y, max_x - min_x)
# 한 변의 길이를 유지하는 최소의 좌상단 좌표를 가지는 직사각형 좌표 구하기
min_y = max(max_y - side_len, 0)
max_y = min_y + side_len
min_x = max(max_x - side_len, 0)
max_x = min_x + side_len
rectangles.append((side_len**2, min_y, min_x, max_y, max_x))
# 우선순위 : 넓이 > 좌상단 y좌표 > 좌상단 x좌표
return min(rectangles)[1:]-
주의할 점은 크게 두가지입니다.
- 정사각형의 넓이는 가장 작아야 한다.
- 가장 작은 넓이의 정사각형이 여러 개일 경우 좌상단 좌표가 가장 작은 정사각형을 선택한다.
-
특정 참가자 좌표와
E사이의 좌상단 좌표가 가장 작은 정사각형의 좌표를 구하는 과정을 그림으로 설명해보겠습니다.-
다음과 같이
E는 (2, 1), 참가자는 (0, 1)인 상황을 가정해보겠습니다.
-
우리는 좌상단 좌표가 최대한 (0, 0)과 가까운 정사각형을 얻어야합니다. 그러면
E와 참가자의 좌표 중 y, x 값이 큰 좌표가 가장 우측 하단으로 멀어져야 할 것이고, 이를 위해서 단순하게 두 좌표 중 max_y, max_x 좌표에 변의 길이를 빼었을 때의 좌표를 좌상단 좌표로 생각하면 되겠죠. -
하지만 위의 경우에 변의 길이인 2를 빼었을 때는 0을 벗어나 버립니다.
-
차선책으로 0을 벗어나지 않는 첫 좌표를 선택할 수 있겠네요.
-
- 이렇게 구해낸 정사각형의 정보는 아래와 같이 저장합니다.
rectangles.append((side_len**2, min_y, min_x, max_y, max_x))
- 모든 정사각형 중 위에서 설명드린 주의할 점을 만족시키는 정사각형 하나를 찾을 수 있도록 min 함수를 사용하기 위함입니다.
return min(rectangles)[1:]
정사각형의 좌표를 알아냈으면 이제 회전시켜야 합니다.
rotate()
def rotate(min_y: int, min_x: int, max_y: int, max_x: int) -> None:
"""
rotate시킬 정사각형의 좌표를 받아 시계방향으로 90도 회전시킨다.
input : rotate 시킬 정사각형의 min_y, min_x, max_y, max_x 좌표
output : x
"""
global E
participants_set = set(participants)
# rotate 시킬 부분의 임시 matrix
rotate_matrix = [
[0 for _ in range(min_x, max_x + 1)] for _ in range(min_y, max_y + 1)
]
# rotate전 정보 백업
for y in range(min_y, max_y + 1):
for x in range(min_x, max_x + 1):
# 벽의 경우 내구도 -1 시켜 백업
if matrix[y][x] > 0:
rotate_matrix[y - min_y][x - min_x] = matrix[y][x] - 1
# 출구 좌표 정보 백업
elif (y, x) == E:
rotate_matrix[y - min_y][x - min_x] = "E"
# 참가자 좌표 정보 백업
elif (y, x) in participants_set:
# 참가자는 동일 좌표에 여러명이 위치할 수 있음
cnt = 0
while (y, x) in participants:
cnt += 1
participants.remove((y, x))
# 참가자 한 명당 *의 개수로 백업
rotate_matrix[y - min_y][x - min_x] = "*" * cnt
# 해당 백업 matrix 90도 회전
rotate_matrix = [list(row)[::-1] for row in zip(*rotate_matrix)]
# 원본 matrix의 정사각형 위치를 90도 회전시킨 백업 matrix로 대치
for y in range(min_y, max_y + 1):
for x in range(min_x, max_x + 1):
# 회전 후 참가자 위치를 다시 큐에 삽입
if str(rotate_matrix[y - min_y][x - min_x]).startswith("*"):
# 기존 존재하던 참가자 수만큼 삽입
for _ in range(len(rotate_matrix[y - min_y][x - min_x])):
participants.append((y, x))
matrix[y][x] = 0
# 회전 후 출구 위치
elif rotate_matrix[y - min_y][x - min_x] == "E":
E = (y, x)
matrix[y][x] = 0
# 회전 후 벽의 내구도
else:
matrix[y][x] = rotate_matrix[y - min_y][x - min_x]-
정사각형의 크기만큼 백업 matrix를 정의해서 rotate 전의 벽의 내구도, 참가자 좌표, 출구 좌표를 백업합니다.
- 이 때 벽의 내구도는 1 감소시켜서 기록합니다.
- 주의할 점은 같은 좌표에 위치한 참가자도 있을 수 있다는 점입니다. 따라서 rotate 전 특정 위치에 존재한는 참가자의 정보를
participants에서 모두 빼고, 뺀 숫자만큼 "*"로 백업 매트릭스에 기록합니다.
-
백업 matrix를 시계방향으로 90도 회전시킵니다.
- 새로 형성되는 row는 기존 col을 거꾸로 한 것이라고 생각하면 편합니다.
rotate_matrix = [list(row)[::-1] for row in zip(*rotate_matrix)]
- 새로 형성되는 row는 기존 col을 거꾸로 한 것이라고 생각하면 편합니다.
-
회전시킨 백업 matrix의 좌표에 맞춰 원본 matrix를 업데이트 해줍니다.
-
이 때, 참가자의 좌표도 업데이트 해서 "*" 개수만큼
participants에 삽입해주어야 합니다. -
출구도 마찬가지로 기록된 정보를 바탕으로 업데이트 해줍니다.
🟠 후기
- 처음으로 구현이 까다롭다고 악명 높은 삼성 SW 역량 테스트의 기출 문제를 풀어보았습니다..
- 수 많은 예외와 놓친 조건, 코드 실수 덕에 꼬박 2일에 걸쳐 구현해낼 수 있었던 것 같습니다.
- 느꼈던 점은 이렇게 문제가 구현이 까다롭고 복잡할 수록, 사전에 solution을 설계해서 어떻게 메서드를 구현할지 충분하게 생각하고 코드 작성에 들어가는 게 무척 중요하다는 점입니다.
- 또한, 코드를 작성하면서 docstring과 type hint를 작성하는 습관을 다지고 있는데 정말 도움되는 것 같습니다.
- 이번 문제의 코드를 제가 생각하기에 너무 복잡하게 구현한 감이 없지않아 있지만! 꾸준히 발전해나가겠습니다.
전체 코드를 참고하실 분은 아래 제가 참여하고 있는 알고리즘 스터디 Repository를 확인해주세요!
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.
Grow Exponentially