국문과 유목민

1. 문제 설명 N개의 강의 중 선수 강의가 있을 경우 특정 강의가 주어졌을 때, 해당 강의를 듣기 위해서 걸리는 최소한의 시간을 구하는 문제 - 위상정렬을 이용하는 문제로 위상정렬 이론에서는 리턴하는 값이 순서였다면, 이번에는 cost이다. 하지만 알고리즘 상에서 큰 변경점은 없다. 단지, 시간의 정보를 담은 리스트 변수가 하나 필요하다. 또한, 초기 input값 처리 부분을 고려하면 될 것으로 보인다. 2. 코드 from collections import deque import copy n = int(input()) indegree = [0]*(n+1) graph= [[] for _ in range(n+1)] time = [0]* (n+1) # 방향 그래프의 간선 정보 입력 받기 for i in ra..

1. 문제 설명 도시와 도시가 연결되어 있을 때 전보를 보내는 경우 얼마나 많은 도시에 보낼 수 있으며, 가장 먼 거리는 얼마인지 구하는 문제이다. - 다익스트라 알고리즘을 활용한 문제로 heapq를 활용한다. 2. 코드 import heapq # 입력 INF = int(1e9) a, b, start = map(int, input().split()) graph = [[] for _ in range(a+1)] distance = [INF]*(a+1) for _ in range(b): x, y, z = map(int, input().split()) graph[x].append((y, z)) # 노드, 거리 # 다익스트라 알고리즘 def dijkstra(start): q = [] heapq.heappush(q..