조용하지않는개발Blog

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 풀이 문제를 보았을때 알수있는 힌트 요즘 다익스트라 문제를 많이 푸는것같은데 리스트에 거리가 있는 경우는 거의 다익스트라 알고리즘으로 풀면 되는 문제인듯하다. 최단 시간에 오는 문제로 모든 학생들의 정해진 위치까지의 최단 거리와 다시 돌아가는 거리를 더해서 가장 오래걸리는 학생의 소요시간을 출력하면 되는 문제이다. import sys import heapq INF =..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 1. 방향성이 없음(양쪽을 다 갈수있음) 2. 1에서 n까지의 최단 거리를 알고싶어함. 3. 이동간의 거리가 존재한다. 4. 정해진 2곳을 지나가야한다. 1과 3번을 통해서 다익스트라 알고리즘을 이용하면 된다는 것을 알수있다. 4번을 통해서 다익스트라를 2번더 반복해서 최소 거리를 찾으면 해결되는 문제이다. 기본 다익..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 그래프, 각 비용이 존재하고 최소 비용을 구하는 문제이면 힙큐를 사용한 다익스트라 알고리즘을 이용해서 푸는 문제일 확률이 높음. 이를 참고 하여 문제를 풀면 통과할 것입니다. import sys import heapq INF = sys.maxsize input = sys.stdin.readline def solve(): n = ..

다익스트라 알고리즘은 모든 정점까지의 최단 경로를 구할때 사용하는 알고리즘이다. 다익스트라 알고리즘은 그 방식이 효육적이라 그래프가 큰 경우에도 사용 가능한 장점이 있다. 그림을 그리기에는 시간이 많이 걸리니 나무위키의 그림을 가져와서 이야기 하겠습니다. A에서 시작한다는 가정하에 최단 거리를 찾아봅시다. 먼저 다익스트라 알고리즘은 아직 확인 되지 않은 거리는 전부 무한으로 해놓습니다. 첫 루프를 돌리면 위와 같이 a->b가는 거리는 10, a->c가는 거리는 30 a->d로 가는 거리는 15가 되는 것을 알수있다. 이때 리스트에는 b,c,d가 쌓이게 된다. a의 모든 루프는 끝이 났다. 다음으로는 b,c,d 중 하나를 이동하면 되는데 이때 거리가 최소인것을 먼저 진행한다. 거리가 10인 B를 먼저 시작..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보면 그래프 문제라는 것을 알수있다. 또한 방향이 정해져있고, 정점으로가는 최단 경로를 구하는 문제이다. 간단하게 생각하면 BFS나 DFS로 풀면 되지 않을까? 생각하고 풀면 시간초과가 난다. 리스트로 정리해서 코드를 돌리면 최단 거리가 아닌 것들도 다 건드리면서 계산 되기때문이다. 또한 필요한 최단 경로만 알면 되기..