Problem Solving/백준

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

돌돌김 2021. 2. 14. 22:49

www.acmicpc.net/problem/20168

 

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

첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의

www.acmicpc.net

 

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

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

 

  • 가진 돈을 목적지까지 도착하기 전에 전부 사용하지 않기
  • 목적지에 도착했다면 지금까지 지나온 노드 중 가장 비용이 큰 값이 어떤 것인가?
    • 목적지에 도착하는 길이 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)

1 2 3 4 5 6 7 8 ··· 64