[Python] 백준 1347번: 미로 만들기

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

 

 

 

[풀이]

명령어의 길이는 0보다는 크고, 50보다는 작다.

그러면 가장 최악의 케이스는 F가 49번 있는 것.

방향이 동, 서, 남, 북으로 이동할 수 있기 때문에 현재 위치로부터 +49까지.

 

때문에, 현재 위치로부터 동, 서, 남, 북으로 49칸씩 확장해서 최대 100 x 100 칸의 배열을 미리 만들어두었다.

그리고 그 위치로부터 최소 y, x 범위와 최대 y, x 범위만큼을 이동할 때마다 확인해서

최종적으로 이동한 경로에 대한 n * m 범위에 대해 출력하였다.

 

그렇게 어렵지 않은 구현 문제.

 

다만 하나 주의할 점은, 50, 50으로 지정한 최초 시작 지점을 '.' 으로 초기화 하는 것을 잊지 말아야 한다.

 

 

 

[코드]

n = int(input())
c = list(input())

min_y, min_x = 50, 50
max_y, max_x = 50, 50
y, x = 50, 50
board = [['#'] * 100 for _ in range(100)]

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

board[50][50] = '.'
for command in c:
    if command == 'L':
        dir = ((dir + 4) - 1) % 4
    elif command == 'R':
        dir = ((dir + 4) + 1) % 4
    elif command == 'F':
        y += dy[dir]
        x += dx[dir]
        board[y][x] = '.'

        min_y, min_x = min(min_y, y), min(min_x, x)
        max_y, max_x = max(max_y, y), max(max_x, x)

for i in range(min_y, max_y + 1):
    for j in range(min_x, max_x + 1):
        print(board[i][j], end='')
    print()

 

 

 

[시간복잡도]

O(N)