[BOJ][Python]1347 풀이

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

1347번: 미로 만들기

def f(mx, my):
    for i in range(my+1):
        for j in range(mx+1):
            labyrinth = [['#' for _ in range(mx+1)] for _ in range(my+1)]
            posx, posy = j, i
            labyrinth[posy][posx] = '.'
            for k in route:
                if 0 <= k[0] + posy <= my and 0 <= k[1] + posx <= mx:
                    labyrinth[posy+k[0]][posx+k[1]] = '.'
                else:
                    break
            else:
                return labyrinth
                
direction = [(1,0), (0,-1), (-1,0), (0,1)]
route = [(0,0)]
n = int(input())
log = input()
d = 0
pos = [0, 0]
for i in log:
    if i == 'R':
        d += 1
    elif i == 'L':
        d -= 1
    else:
        pos[0] += direction[d%4][0]
        pos[1] += direction[d%4][1]
        route.append((pos[0], pos[1]))
my = max([i[0] for i in route]) - min([i[0] for i in route])
mx = max([i[1] for i in route]) - min([i[1] for i in route])
ans = f(mx, my)

for i in ans:
    print(''.join(i))

오늘도 어김없이 바보짓을 했습니다. *list를 하면 언패킹하면서 자동으로 띄어쓰기가 붙는 걸 깜빡했어요. 분명 결과가 맞는데 왜 자꾸 틀리는지 한참 고민하다가 제 결과가 너무 비율이 딱 맞는게 이상해서 join을 해봤더니 되네요. 여러분은 결과에 공백이 없다는 점에 주의해주세요.

 

이 문제에서 어려운 부분은 미로의 크기도 따로 주어지지 않고, 어디가 시작점인지도 모르고, 미로가 직사각형이라는 부분이라고 생각합니다. 처음부터 배열 사이즈를 만들어놓고 시작을 못하니 나름대로 해당 부분을 어떻게 처리할지 고민을 해야하죠.

 

저 같은 경우는 입력을 다 따라가면서 4방향으로 가장 끝까지 갔던 위치를 체크해서 그걸로 배열 크기를 정한 다음에, 이중반복문을 사용해서 계속 시작 위치를 바꿔가면서 가능한 경우(미로의 모든 이동가능한 칸을 다 방문했을 때의 기록이기 때문에)를 찾았습니다.

 

뭔가 문제에서 정해주지 않은 부분을 어떻게 할지 고민하는게 어려웠던 문제입니다. 그 부분만 해결되면 단순한 브루트포스와 크게 다르지 않은 것 같아요.

 

추가// 다른 분들 코드를 살펴보니 100*100의 배열을 만들어서 중간에서 출발한 다음 끝으로 갔던 위치를 체크해뒀다가 해당 사이즈만큼 잘라내어 출력하는 방법으로 작성하신 분들이 엄청 많더라구요. 굉장히 좋은 방법인 것 같습니다. 처음부터 딱 맞는 사이즈를 만들어놓고 될 때까지 반복문을 실행하는 거 보다 넉넉하게 만들어서 돌아다니게 한 다음 필요한 부분만 잘라내는 쪽이 배열의 메모리 측면에서는 조금 낭비일지도 모르지만 코드의 난이도나 고민하는 시간 면에서 훨씬 효율적인 것 같네요.