문제
사람이 남쪽을 바라보고 서 있을 때, R(오른쪽 회전), L(왼쪽 회전), F(전진) 명령어를 수행한 경로를 기반으로 미로를 출력하라. 방문한 칸은 ., 나머지는 #으로 표시한다.
입력
첫째 줄에 명령어 길이, 둘째 줄에 명령어 문자열이 주어진다.
출력
미로를 최소 크기의 직사각형으로 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 RRFRF | .# .. |
풀이
명령어를 시뮬레이션하여 방문 좌표를 기록하고, 좌표를 보정하여 2차원 배열에 미로를 그린다.
- 초기 방향을 남쪽(1)으로 설정하고 (0,0)에서 출발한다
- R/L은 방향을 90도 회전, F는 현재 방향으로 한 칸 전진하며 좌표를 기록한다
- 기록된 좌표의 최솟값으로 보정하여 양수 인덱스로 변환한다
- 최소 크기의 2차원 배열을 만들고, 방문 좌표는
., 나머지는#으로 채운다
핵심 아이디어: 방문 좌표의 최소/최대로 배열 크기를 결정하고, 좌표 보정으로 음수 인덱스 문제를 해결한다.
코드
import sys
length = int(sys.stdin.readline())
note = list(sys.stdin.readline().rstrip())
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
x, y, direction = 0, 0, 1
graph = [[x, y]]
for i in note:
if i == "R":
direction = (direction + 1) % 4
if i == "L":
direction = (direction - 1) % 4
if i == "F":
x = x + dx[direction]
y = y + dy[direction]
graph.append([x, y])
n = max(graph)[0] - min(graph)[0] + 1
m = max(graph, key=lambda x: x[1])[1] - min(graph, key=lambda x: x[1])[1] + 1
min_x = min(graph, key=lambda x: x[0])[0]
min_y = min(graph, key=lambda x: x[1])[1]
for i in graph:
i[0] = i[0] + abs(min_x)
i[1] = i[1] + abs(min_y)
map = [[False] * m for _ in range(n)]
for i in graph:
if map[i[0]][i[1]] == False:
map[i[0]][i[1]] = "."
for i in map:
for j in range(m):
if i[j] == False:
i[j] = "#"
for i in map:
for j in range(len(i)):
print(i[j], end="")
print("")복잡도
- 시간: O(N) (N은 명령어 길이)
- 공간: O(N)