[백준/1347] 미로 만들기 (Python)

Problem : https://www.acmicpc.net/problem/1347

1347번: 미로 만들기

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:08:43

 

---

 

문제 설명

 

홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의 움직임을 모두 노트에 쓰기로 했다. 홍준이는 미로의 지도를 자기 노트만을 이용해서 그리려고 한다.

입력으로 홍준이가 적은 내용을 나타내는 문자열이 주어진다. 각 문자 하나는 한 번의 움직임을 말한다. ‘F’는 앞으로 한 칸 움직인 것이고, ‘L'과 ’R'은 방향을 왼쪽 또는 오른쪽으로 전환한 것이다. 즉, 90도를 회전하면서, 위치는 그대로인 것이다.

 

입력 및 출력

 

입력

첫째 줄에 홍준이가 적은 내용의 길이가 주어진다. 길이는 0보다 크고, 50보다 작다. 둘째 줄에 홍준이가 적은 내용이 내용이 주어진다.

 

출력

첫째 줄에 미로 지도를 출력한다. ‘.’은 이동할 수 있는 칸이고, ‘#’는 벽이다.

 

입력 예시

 

5
RRFRF

 

출력 예시

 

..
.#

 

 

 

---

 

풀이

 

초기 위치를 (0, 0)으로 잡고, 이동하는 좌표 및 방향 변화를 체크하도록 해 보자. 이 때 x좌표와 y좌표의 최댓값 및 최솟값을 저장하도록 한다.

 

모든 탐색이 종료된 후 총 지도의 크기는 (x좌표의 최소 - 최대차 + 1, y좌표의 최소 - 최대차 + 1)가 된다. 또한, 방문할 수 있는 모든 지점을 방문했다는 전제가 있으므로 앞서 이동한 좌표들은 '.'으로 표기해주면 된다. 이 때 각 좌표는 최솟값을 빼 줌으로써 보정할 수 있다.

 

 

풀이 코드

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


n = int(input())
moves = input().strip()
min_x, max_x, min_y, max_y = 0, 0, 0, 0
x, y, k = 0, 0, 0
travel_set = set([(0, 0)])

for move in moves :
  if move == 'L' :
    k = (k - 1) % 4
  elif move == 'R' :
    k = (k + 1) % 4
  else :
    x += dx[k]
    y += dy[k]
    travel_set.add((x, y))
    min_x = min(x, min_x)
    max_x = max(x, max_x)
    min_y = min(y, min_y)
    max_y = max(y, max_y)

map_list = [['#']*(max_x - min_x + 1) for _ in range(max_y - min_y + 1)]
for x, y in travel_set :
  map_list[y - min_y][x - min_x] = '.'
for _map in map_list :
  print(''.join(_map))

풀이 완료!