[python]백준 17836번 : 공주님을 구해라!

공주님을 구해라!

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2397	551	418	22.012%

문제

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈를 반드시 하고 싶은 용사는 T시간 내에 반드시 공주님이 있는 곳으로 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸리며, 공주님이 있는 곳에 정확히 T초만에 도달하는 경우도, 구출 할 수 있다.

성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

입력

첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 5000)

두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

출력

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.

만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.

나의 답

# 공주님 구하기

n,m,t = map(int,input().split())
map_arr = list()
for i in range(n):
    map_arr.append(list(map(int,input().split())))
max_num = 987654321

time_knife = int(t)

def findRoute(map_tmp, time, loc_y, loc_x):
    global time_knife

    if loc_y==n-1 and loc_x==m-1: # 공주에게 도착
        #print('arrive')
        return time
    if map_arr[loc_y][loc_x]==2: # 검에 도착
        #print('knife')
        time_knife = time+(n-loc_y-1+m-loc_x-1)
        return time_knife
    if time>time_knife: # 시간 초과
        #print('time out')
        return max_num

    save_value = map_tmp[loc_y][loc_x]
    map_tmp[loc_y][loc_x]=1

    tmp1 = max_num
    tmp2 = max_num
    tmp3 = max_num

    loc_x = loc_x+1
    if loc_y<n and loc_x<m and loc_y>=0 and loc_x>=0:
        if map_tmp[loc_y][loc_x]!=1: 
            tmp1 = findRoute(map_tmp, time+1,loc_y,loc_x) #오른쪽
    loc_x = loc_x-1
    loc_y = loc_y+1
    if loc_y<n and loc_x<m and loc_y>=0 and loc_x>=0:
        if map_tmp[loc_y][loc_x]!=1: 
            tmp2 = findRoute(map_tmp, time+1,loc_y,loc_x) #아래
    loc_x = loc_x-1
    loc_y = loc_y-1
    if loc_y<n and loc_x<m and loc_y>=0 and loc_x>=0:
        if map_tmp[loc_y][loc_x]!=1: 
            tmp3 = findRoute(map_tmp, time+1,loc_y,loc_x) #왼쪽
    loc_x = loc_x+1
    loc_y = loc_y
    if min(tmp1,tmp2,tmp3)!=max_num:
        map_tmp[loc_y][loc_x]=save_value
    return min(tmp1,tmp2,tmp3)



tmp_ans =findRoute(map_arr,0,0,0)
if tmp_ans==max_num:
    print('Fail')
else:
    print(tmp_ans)

재귀 함수로 구현해서 m,n에 도달할 때 return, 검에 도달해도 계산해서 return, time이 초과되도 return하는 방식으로 진행

완전 탐색 => 경로의 수가 3^(10000) 이라 불가능

조건 주고 완전 탐색 => 주어진 시간 내에 수행하려면 3^(5000) 의 시간 복잡도라 불가능

분할 정복 => 불가능

완전 탐색으로 구현하려고 보니 어떻게 계산을 해봐도 시간 초과라 안되는 걸 알면서도 일단은 조건을 최대한 주고 구현해보았다. 저번 시간에 배운 다이나믹 프로그래밍 을 응용할 생각을 못했다.

다이나믹 프로그래밍 : 계산한 값을 저장해두고 바로 꺼내쓸 수 있도록 하는 프로그래밍

BFS로 경로를 찾는 알고리즘을 만드는 것은 동일하나, 여러 변수를 계속 넘겨 받으면서 조건을 검사하는 것이 아니라 다이나믹 프로그램이 방식으로 그 지점까지 걸리는 시간을 직접 저장하는 것이 이 문제의 포인트였다.

깨달은 점

항상 문제를 보고는 해결하려고만 들지 자료구조, 메모리를 사용할 생각을 못하는 것 같다. 앞으로는 문제를 보고 구현 방법을 생각할 때 '다이나믹 프로그래밍'도 고려를 해보고 여러 자료구조를 활용할 방법을 생각해봐야겠다!