다익스트라11

• 

  [백준/BOJ] 5972번: 택배 배송 문제 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 해설 전형적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘을 통해 1번 헛간에서 시작하여 마지막 헛간에 도착했을 때의 최소 비용을 구해 출력하면 된다. 다익스트라 알고리즘을 잘 모른다면 이 글을 읽어보는 것을 추천한다. 코드 import java.util.* import kotlin.collections.ArrayList private lateinit var graph: Array private.. PS(Problem Solving)/BOJ 2022. 9. 7.

• 

  [백준/BOJ] 14938번: 서강그라운드 문제 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 해설 어떠한 지역에 떨어졌을 때, 수색 범위 안에서 가장 많은 아이템을 얻을 수 있는지를 구하는 문제이다. 우선 모든 지역에서의 범위를 구해야 하기 때문에 1번 지역에 떨어졌을 때 모든 지역까지의 거리를 구해야 하고, 2번 지역에 떨여졌을 때 모든 지역까지의 거리, 3번, 4번 . . . n번에 떨어졌을 때의 모든 지역까지의 거리를 구해야 한다. 모든 지역까지의 거리를 구하는 알고리즘으로 다익스트.. PS(Problem Solving)/BOJ 2022. 8. 29.

• 

  [백준/BOJ] 1082번: 해킹 문제 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 해설 한 컴퓨터가 해킹당했고, 이 컴퓨터에 의존하는 컴퓨터들은 시간이 지남에 따라 전염되기 시작한다. 즉, 한 개의 루트 노드로부터 연결된 노드들이 전부 감염된다는 것이다. 이를 풀기 위해 다익스트라 알고리즘을 응용하였다. 다익스트라 알고리즘은 최단 경로를 찾는 알고리즘으로 PriorityQueue를 이용하여 수행해나간다. 하지만 이 문제에서 a, b는 두 번 이상 주어지지 않는다. 즉, 최단 .. PS(Problem Solving)/BOJ 2022. 8. 21.

• 

  [백준/BOJ] 11779번: 최소비용 구하기 2 문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 해설 https://jjunsu.tistory.com/249에서 했던 1916번: 최소비용 구하기 문제의 상위 버전이다. 최소 비용을 구한 후, 몇 개의 도시를 거쳤는지, 어떤 도시를 방문했는지를 같이 출력해야 한다. 최소 비용을 구하는 방법은 위 문제와 같이 다익스트라 알고리즘을 사용하여 구하면 된다. 이제 어떠한 도시를 거쳤는지 경로를 알아야 한다. 어렵게.. PS(Problem Solving)/BOJ 2022. 8. 10.

• [백준/BOJ] 4485번: 녹색 옷 입은 애가 젤다지? 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 해설 bfs로도 풀 수 있을 것 같았지만, 다익스트라를 사용해서 문제를 풀었다. 각 칸의 소지금을 우선순위 큐에 오름차순으로 기준을 잡아준다. 기본적인 다익스트라 알고리즘 문제이다. 소스 코드 import java.lang.StringBuilder import java.util.* private lateinit var map: Array private val dx = int.. PS(Problem Solving)/BOJ 2022. 8. 7.

• [백준/BOJ] 1504번: 특정한 최단 경로 문제 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 -> v1 -> v2 -> n 1 -> v2 -> .. PS(Problem Solving)/BOJ 2022. 8. 5.

• [백준/BOJ] 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 해설 문제의 핵심을 찾아보면 다음과 같다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 최단 시간에 오고 가기를 원한다. 단방향이기 때문에 오고 가는 길이 다를지도 모른다. 최단 시간을 구하는 문제이기에 다익스트라 알고리즘을 이용하면 된다. 파티를 갔다가, 다시 집에 돌아오는 시간까지 계산해야 하기 때문에, 각 노드 당 2번.. PS(Problem Solving)/BOJ 2022. 8. 4.

• [백준/BOJ] 1854번: K번째 최단경로 찾기 문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 해설 다익스트라 알고리즘을 이용해서 풀 수 있는 문제이다. 이 문제에서는 각 노드마다 우선순위 큐를 두어 이 노드를 방문할 때마다의 시간을 저장할 것이다. val time = Array(cityCnt + 1) { PriorityQueue(reverseOrder()) } 이 때, 큰 수가 top에 오도록 해야 한다. 즉 내림차순이어야 한.. PS(Problem Solving)/BOJ 2022. 8. 3.

• [백준/BOJ] 1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해설 A번째 도시에서 B번째 도시로 가는데 필요한 최소 비용을 구하는 문제이다. 따라서 다익스트라 알고리즘을 사용하면 된다. 한 도시에서 다른 도시로 가는 버스는 다시 돌아오지 않으므로 단방향이다. 따라서 다익스트라를 진행하기 위한 그래프를 설정할 때 양방향이 아닌 단방향으로 비용을 저장해주면 된다. 다익스트라를 다 수행하고 특정 도시까지 최소 비용을 출력해.. PS(Problem Solving)/BOJ 2022. 8. 3.

• [백준/BOJ] 1753번: 최단경로 문제 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 해설 다익스트라 알고리즘을 사용하여 해결할 수 있는 문제이다. 문제에서 방향그래프가 주어진다고 되어있다. 따라서 단방향으로만 그래프를 설정해주면 된다. 다익스트라 알고리즘을 잘 모른다면 다익스트라 알고리즘 글을 읽어보면 이 문제를 쉽게 풀 수 있을 것이다. 소스 코드 import java.util.* import kotlin.collections.Arra.. PS(Problem Solving)/BOJ 2022. 8. 3.

• 

  [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘(Dijkstra Algorithm)은 다이나믹 프로그래밍을 활용하는 대표적인 최단 경로를 찾는 알고리즘이다. 다만 다익스트라 알고리즘은 음의 간선을 포함할 수 없다. 즉, 음의 간선이 하나라도 포함되어 있다면, 다익스트라 알고리즘을 사용할 수 없다. 원래 다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이다. 하지만, 일반적으로 한 꼭짓점을 루트(root) 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 알고리즘으로 최단 경로 트리를 만든다. 동작 단계 출발 노드를 설정한다. 최단 거리를 저장할 테이블을 초기화해준다.(보통 무한대(아주 큰 값)로 초기화한다.) 현재 위치하고 있는 노드의 인접 노드 중 비용이 가장 적은 노드를 선택한다. 해당 .. Algorithm 2022. 8. 3.