백준
1.[백준] 1261번 알고스팟
https://www.acmicpc.net/problem/1261다익스트라 알고리즘을 활용하여 문제 풀었다2차원 배열을 그래프로 나타내고, 동서남북 방향을 간선으로 전환하여 풀어보았다
2.[백준] 1238번 파티
https://www.acmicpc.net/problem/1238다익스트라를 활용하여 x에서 각자의 집까지 거리 'x->집'을 구한다반대로 1번 학생부터 집에서 x까지 '집->x'를 'x->집'과 더한다. 이러면 왕복 거리를 구할 수 있다범위 1부터 끝까지 m
3.[백준] 1916번 최소비용 구하기
https://www.acmicpc.net/problem/1916다익스트라를 활용하면 쉽게 풀 수 있다
4.[백준] 1753번 최단경로
https://www.acmicpc.net/problem/1753전형적인 다익스트라 문제다. 주의할 점은 input = sys.stdin.readline 을 통해서 시간을 줄여야 된다는 점!
5.[백준] 1504번 특정한 최단 경로
https://www.acmicpc.net/problem/1504방향성이 없는 그래프이기 때문에 양방향으로 간선을 추가한다다익스트라 알고리즘을 활용하여 1 -> v1 -> v2 -> n 과 1 -> v2 -> v1 -> n의 경우를 나누어서 각 이동거리 최소
6.[백준] 13549번 숨바꼭질3
https://www.acmicpc.net/problem/13549먼저 n과 m의 범위가 100000까지이지만 +1하고, 순간이동 시에 \*2까지 범위가 필요하니 넉넉하게 200002로 최대 범위를 지정한다그런 다음 0부터 +-1과 \*2를 해도 index가
7.[백준] 4485번 녹색 옷 입은 애가 젤다지?
문제 코드 풀이
8.[백준] 18352번 특정 거리의 도시 찾기
https://www.acmicpc.net/problem/18352다익스트라 알고리즘을 통해서 먼저 시작점에서의 최단거리 테이블을 만든다그리고 만든 테이블에서 이동 비용이 k인 값이 없으면 -1을 출력하고, 아니라면 인덱스 값을 출력한다
9.[백준] 11779번 최소비용 구하기 2
https://www.acmicpc.net/problem/11779다익스트라를 활용해서 풀면되는데 다른 문제들과 차이점은 경로를 출력해야한다는 점이다다익스트라 메소드 안에 distance_path를 정의하고, heap에 넣는 값에 경로 값도 추가한다이러면 최소
10.[백준] 2665번 미로만들기
https://www.acmicpc.net/problem/2665먼저 graph를 입력받고 1과 0을 바꾸어 2차원 배열을 만든다그러면 1일 경우 이동거리 1을 더하면 되니 다익스트라를 이용하여 최소 비용을 구한다
11.[백준] 2252번 줄 세우기
https://www.acmicpc.net/problem/2252이 문제는 위상 정렬을 이용하면 손쉽게 해결할 수 있다위상 정렬은 큐로 구현하며, indegree가 0일 경우 큐에 넣어 문제를 풀어나간다
12.[백준] 1005번 ACM Craft
문제 https://www.acmicpc.net/problem/1005 코드 풀이 이 문제는
13.[백준] 10282번 해킹
https://www.acmicpc.net/problem/10282이 문제는 다익스트라 알고리즘을 이용해서 해결이 가능하다다익스트라 알고리즘에서 path를 저장한다. 그리고 path에서 최초로 감염된 컴퓨터 c가 있는 것을 카운트해서 문제를 해결한다
14.[백준] 1197번 최소 스패닝 트리
https://www.acmicpc.net/problem/1197먼저 파라미터를 모두 입력 받는다간선을 비용을 기준으로 오름차순으로 정렬한다그리고 모든 간선에 대해서 a와 b의 부모가 같지 않다면 서로 연결되지 않은 것이므로 연견을 진행 해줄건데 비용으로 정렬
15.[백준] 1922번 네트워크 연결
https://www.acmicpc.net/problem/1922최소 신장 트리 예제와 똑같은 문제. 최소 신장 트리 알고리즘을 이용해서 해결했다
16.[백준] 1647번 도시 분할 계획
https://www.acmicpc.net/problem/1647크루스칼 알고리즘을 이용해 최소 신장 트리를 구한다. 그리고 두 마을로 나누기 위해 비용이 가장 많이 드는 간선을 제외하고 결과를 구한다
17.[백준] 4386번 별자리 만들기
https://www.acmicpc.net/problem/4386이 문제는 크루스칼 알고리즘을 이용한 최소 신장 트리 변형 문제다먼저 별들의 좌표를 입력받고, 각 별에서 다른 별로의 거리를 구하여 graph를 만든다이 후에는 크루스칼 알고리즘을 이용해 답을 구
18.[백준] 2887번 행성 터널
https://www.acmicpc.net/problem/2887이 문제는 크루스칼 알고리즘 이용해서 풀 수 있다하지만 모든 노드에서 다른 노드로의 간선을 구할 시에 최대 100000 \* (100000 - 1) / 2개의 간선이 구해진다이를 줄이고자 노드대
19.[백준] 1774번 우주신과의 교감
https://www.acmicpc.net/problem/1774이 문제는 이미 연결된 간선들을 제외하고, 새로 이어줄 간선의 최소 비용만 구하면 된다그래서 이미 연결된 간선을 입력받고 그 간선을 union_parent 해준 다음에 최소 신장 트리 알고리즘을