[BOJ 백준] 20168번 : 골목 대장 호석 - 기능성(Python, 파이썬)

www.acmicpc.net/problem/20168

20168번: 골목 대장 호석 - 기능성

 

다익스트라 문제를 풀려고 했는데, 백트래킹으로 풀었다. 

처음에는 문제의 설명이 조금 헷갈렸는데, 고려해야할 조건은 다음과 같았다.

 

• 가진 돈을 목적지까지 도착하기 전에 전부 사용하지 않기
• 목적지에 도착했다면 지금까지 지나온 노드 중 가장 비용이 큰 값이 어떤 것인가?
  • 목적지에 도착하는 길이 2개 이상인 경우 가장 비용이 큰 값 중 최소가 정답

 

위의 조건들을 백트래킹에 맞게 풀어주면 되는 문제였다. 왜 태그에 백트래킹이 없는지 모르겠다

 

 

소스코드

 

import sys

n, m, a, b, c = map(int, input().split())

board = [[] for _ in range(n+1)]
visited = [[False] for _ in range(n+1)]
answer = sys.maxsize    

def dfs(start, end, cost, maxShame):
    visited[start] = True
    global answer
    if start == end:
        answer = min(answer, maxShame)
        return
    for item in board[start]:
        nextNode = item[0]
        nextCost = item[1]
        if visited[nextNode] == True: continue
        if nextCost > cost: continue
        visited[nextNode] = True        
        dfs(nextNode, end, cost - nextCost, max(maxShame, nextCost))
        visited[nextNode] = False

for _ in range(m):
    n1, n2, cost = map(int, input().split())        
    board[n1].append((n2, cost))
    board[n2].append((n1, cost))

dfs(a,b,c,0)

if answer == sys.maxsize:
    answer = -1
print(answer)