백준_1446 (python)

문제에서 N이 최대 12개라는 것을 보자마자  재귀와 백트래킹을 이용하여 풀어보자고 생각을 했습니다.

다 풀고 다른 분들의 풀이를 봤는데 대부분 다익스트라와 dfs를 이용하여 푸셨고 코드 길이도 엄청 간단했습니다.

 이렇게 풀면 고려해야 되는 부분이 많으니 참고용으로만 봐주세요.

 

풀이법

1. 먼저 지름길 시작 지점을 기준으로 data 리스트를 정렬해줍니다.

2. 첫 백트래킹 조건 현 좌표가 도착지점이라면

3. 두번째 백트래킹 조건 idx가 끝까지 왔지만 아직 도착지점에 도달하지 못했을 경우

4. 세번째 백트래킹 조건 현 x좌표가 현 지름길의 시작 지점보다 클 경우(역주행 방지)

 

그 밑에 코드는 다른 백트래킹 문제들의 코드와 유사합니다.

N,D = map(int,input().split())

data = []

for i in range(N):
    s,e,d  = map(int,input().split())
    if e <= D:
        data.append((s,e,d))

leng = len(data)
result = float("inf")

data = sorted(data, key=lambda x:x[0])

def solve(idx,x,count):
    global result
    if x == D:
        result = min(result,count)
        return
    if idx == leng and x < D:
        result = min(result,count+(D-x))
        return
    if x > data[idx][0]: # 역주행하지 말라는 의미이다.
        solve(idx+1,x,count)
    else:
        if x == data[idx][0]: # 현재 바로 지름길을 탈 수 있는 경우
            solve(idx+1,data[idx][1],count+data[idx][2])
        else: # 현재 바로 지름길을 탈 수 없는 경우
            solve(idx+1,data[idx][1],count+data[idx][2]+(data[idx][0]-x))
        # 이제는 현 지름길을 선택하지 않는 경우이다.
        solve(idx+1,x,count)        

solve(0,0,0)
print(result)

조언, 지적 환영하고 감사합니다 (_ _)