[백준] 1240번 노드 사이의 거리 - 파이썬/트리, 백트래킹

JinUk Lee·2023년 6월 2일
0

백준 알고리즘

목록 보기
63/74

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


from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

N,M = map(int,input().split())
tree = defaultdict(list)
root = dict()

def dfs(start,end,visited,dis):
    if start == end:
        print(dis)
        return

    for i in tree[start]:
        if not visited[i]:
            visited[i]=True
            # 두 점 사이의 거리를 찾음
            dis_list = [start,i]
            dis_list.sort()
            dis_list=tuple(dis_list)
            dis+=root[dis_list]
            dfs(i,end,visited,dis)
            
            # 방문 취소 처리하고 거리도 다시 빼줘야한다.
            visited[i]=False
            dis -= root[dis_list]

for i in range(N-1):
    A,B,R = map(int,input().split())
    tree[A].append(B)
    tree[B].append(A)
    
    # 두 점 사이의 거리를 딕셔너리로 만듬
    elem = [A,B]
    elem.sort()
    elem = tuple(elem)
    root[elem]=R

for i in range(M):
    start,end = map(int,input().split())
    visited = [ False ] * (N+1)
    visited[start]=True
    dis=0
    dfs(start,end,visited,dis)

백트래킹으로 쉽게 풀 수 있었다.

딕셔너리의 개념을 정확히 이해하고있지 않아서 막혔다.

딕셔너리의 키는 immutable하고 값은 mutable하다.

처음에 키를 list로 하려고 했다가 막혀서 딕셔너리 자료구조에 대해 찾아보았고, 키를 tuple로 바꿔서 문제를 해결할 수 있었다.

profile
개발자 지망생

0개의 댓글