cotton 블로그 cotton 블로그

백준 골드

• 백준 알고리즘 풀이 (Gold) 1753번, 1655번

  알고리즘 2023. 7. 25. 13:16

  1. 최단 경로 (1753번) 단방향 간선과 간선에 대한 가중치가 주어졌을 때, 시작점에서 다른 정점으로의 최단 경로를 출력하는 문제입니다. 정점에서 다른 정점으로 이동하는 최단 거리를 구하는 문제로 다익스트라 알고리즘을 활용했습니다. 첫 번째 시도 기존의 최단 거리를 구하는 문제들처럼 dfs와 정점까지의 가중치의 합을 저장하기 위한 dp배열을 선언하여 문제를 풀어주었습니다. stack = [[K,0]] dp[K] = 0 while stack: node,weight = stack.pop() for v,w in edges[node]: if weight+w

  Read More