728x90 다익스트라3 [python] 백준 17835 면접보는 승범이네 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 문제 해결 다익스트라를 이용해야 한다는 것은 쉽게 알 수 있다. 그러나 출발점→도착점 이동을 모두 계산하기에는 계산해야하는 양이 많아 시간복잡도에서 걸린다. 따라서 도착점에서 시작해서 각 출발점까지 얼마나 걸리는지 계산하는 것이 더 빠르다. CODE import sys input = sys.stdin.readline import heapq d.. 2023. 9. 29. [python] 백준 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해결 다익스트라 문제 for문을 통해 1~n까지 한 점 i에서 x까지 가는데 최소 시간를 구하고 x에서 i까지 가는데 최소 시간를 구해서 더하면 왕복 최소 시간이 나온다. 리스트를 통해 최댓값을 구하면 된다. CODE import sys input = sys.stdin.readline import heapq INF = sys.maxsize n, m, x = ma.. 2023. 4. 9. [python] 백준 1261 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제해결 다익스트라 (bfs를 이용해 꼭지점간의 최소 거리 측정) 벽이 없는 곳은 벽을 깨지 않으므로 비용(cost)가 이전이랑 같다. 따라서 deque()의 왼쪽에 다시 넣는다. 벽을 부시면 비용(cost)를 추가 지불 해야하므로 deque()오른쪽에 넣는다. deque가 없어질 때 까지 반복한 후 m,n 까지 가는데 비용을 출력한다. CODE import sys from .. 2023. 1. 29. 이전 1 다음 728x90
