반응형 다익스트라3 BOJ 4486 - 녹색 옷 입은 애가 젤다지? / C++ 문제 링크 : https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 다익스트라와 BFS가 섞인 문제이다. 현재 노드에서 이동할 수 있는 경우는 우, 하, 상, 좌 순서로 한칸 씩이다. 먼저, 다익스트라 알고리즘처럼 dist 배열을 모두 INF로 초기화 시킨 뒤 (0, 0)에서 출발한다. 정점을 탐색하며 dist 배열을 업데이트할 수 있다면 업데이트한 뒤 해당 정점으로 이동한다. dist 배열이 모두 업데이트 되었으면 (n-1,.. 2022. 3. 20. BOJ 1238 - 파티 / C++ 문제 링크 : 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 풀이 먼저 X 노드에서 다른 모든 노드들간의 거리를 구한다. 다음으로, 1부터 n번 노드까지 모두 다익스트라를 수행한다. 노드의 개수가 최대 1000개이므로 우선순위 큐로 구현하였다면 시간 초과가 나지 않는다. i번 노드에서 X번 노드까지의 거리를 임시 변수 tmp에 더하고 X번 노드에서 i번 노드까지의 거리도 tmp에 더하면 왕복 거리가 완성되고 이를.. 2022. 3. 20. 다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 최단 경로 문제를 해결할 수 있는 알고리즘 중 하나이다. 최단 경로 문제이므로 각 간선에는 가중치(거리)가 존재하며, 가중치가 음수인 간선이 존재한다면 다익스트라 알고리즘을 사용할 수 없다. 이해를 위해 아래의 예시를 살펴보자 1번 노드부터 모든 경로의 최단거리를 구하려고 한다. 1번 노드에서 본인의 거리는 0이므로 0으로 업데이트한 뒤 나머지 노드까지의 거리는 무한대로 설정한다. 다음으로 1번과 연결된 노드들과의 거리를 업데이트해준다. 연결된 모든 노드들의 거리를 구했으면 가장 짧은 경로로 이동한다. 따라서 위의 예시에서는 5번 노드를 방문하여 다시 거리를 계산한다. 즉, 원래의 distance[4]는 9이지만 distance[5] = 1과 5에서 4로 이동하는 거리 2.. 2022. 3. 17. 이전 1 다음 반응형
