# dijkstra
[개념] 다익스트라 알고리즘(최단거리 알고리즘)
가장 짧은 경로를 찾는 알고리즘을 의미한다.문제상황한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현지점 간 연결된 도로는 그래프에서 간선으로 표현특정한 출발
.png)
<Baekjoon> #4485 BFS, Dijkstra_녹색 옷 입은 애가 젤다지? c++
문제는 (0,0)에서 시작해 (N-1, N-1)까지 갈 때 최소 비용을 구하는 것처음에는 dp를 풀 때 외발뛰기, 삼각형 위의 최대 경로 같은 문제들을 생각하며 dp로 풀어야 하나 생각했지만 링크는 동서남북으로 움직일 수 있으며 그때마다 이미 구했던 최적의 해는 바뀔
[Leetcode]787. Cheapest Flights Within K Stops
There are n cities connected by some number of flights. You are given an array flights where flights\[i] = $from_i$, $to_i$, $price_i$ indicates that
[baekjoon] #1238: 파티
Problem LinkFind all dijkstra results of vertexes.If the start node is same as "x", accumulate all distance results of vertexes.Otherwise, accumulate
[ BOJ / Python ] 10282번 해킹
이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 처음에는 백트레킹을 통해 경우의 수를 따져 구하려고 하였지만 다익스트라로 해결할 때에 훨씬 간단하게 해결할 수 있을 것이라는 생각을 중간에 하였고, 다익스트라로 거리를 체크하여 그 중 가장 큰 수를 걸리는 시간으로,
프로그래머스 배달
N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시
[Algorithm] Shortest Path - 최단경로 알고리즘
최단 경로 알고리즘이란,최단 경로 알고리즘으로 주어진 노드와 간선들 중 가장 짧은 경로를 찾는 알고리즘최단 경로 문제의 종류하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제각 모든 정점에서 다른
<Baekjoon> #1753 Dijkstra_최단경로 c++
\[단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산우선 순위 큐에 지금까지 찾아낸 해당 정점까지의 최단 거리, 정점의 번호를쌍으로 넣음 priority_queue <pair<int, int>> pq; 정점까지의
[Python] 백준 11265 - 끝나지 않는 파티 문제 풀이
분류: Shortest Path (최단거리), Dijkstra(다익스트라), Floyd-Warshall(플로이드와샬)
[ BOJ / Python ] 14938번 서강그라운드
이번 문제는 플로이드-와샬 알고리즘과 다익스트라 알고리즘을 사용하여 두번 풀어보았다. 우선 플로이드-와샬 알고리즘 풀이는 모든 정점에서 모든 정점으로의 최단 거리를 구하여 저장한 후에, 결과값들을 순회하며 최단 거리가 m 이하인 정점에 대한 아이템 수를 더하여 그 중
백준 13549, 숨바꼭질 3 - 다익스트라 / BFS
https://www.acmicpc.net/problem/13549목표 지점을 찾으면 탐색을 종료하는, 일반적인 DFS, BFS는 간선의 가중치가 모두 같아야 함.하지만, 본 문제는 +1, -1 로 가는 경우 가중치가 1,x2 로 가는 경우 가중치가 0 으로
백준 2665, 미로 만들기 - 다익스트라
https://www.acmicpc.net/problem/2665단순히 시작 지점 \[0]\[0] -> 끝 지점 \[n-1]\[n-1]으로의 최단경로는 BFS로 해결 가능.하지만, 방을 바꾸는 최소 개수에 해당하는 경로는 최단경로가 아닐 수 있음시작 지점으로부
백준 1504, 특정한 최단경로 - 다익스트라
https://www.acmicpc.net/problem/1504case 1) 1번 노드 -> v1 노드 -> v2 노드 -> n번 노드1번 노드 -> v1 노드 최단경로 다익스트라v1 노드 -> v2 노드 최단경로 다익스트라v2 노드 -> n번 노드 최단경로
백준 1753, 최단경로 - 다익스트라
https://www.acmicpc.net/problem/1753다익스트라한 노드 -> 다른 모든 노드로의 최단거리음이 아닌 간선의 가중치1) 비용 배열, 우선순위 큐 초기화dist\[]: 시작 노드 거리 0, 나머지 노드 무한대pq: (시작 노드, 0) 추가
[ BOJ / Python ] 1261번 알고스팟
이번 문제는 다익스트라 알고리즘을 통해 쉽게 해결하였다. 기존의 다익스트라 알고리즘 문제와 똑같이 작성을 하고, 힙에 넣을 다음 탐색 구역이 1일 경우에는 비용을 1 증가시켜주고, 그 외에는 비용을 그대로 유지한 상태로 진행시킨다. 이렇게 하면 목적지의 최소 비용을 구
[BOJ] 4485 - 녹색 옷 입은 애가 젤다지?
https://www.acmicpc.net/problem/4485젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!젤다의 전설 시리즈의 주인공
[ BOJ / Python ] 1389번 케빈 베이컨의 6단계 법칙
이번 문제는 바로 이전에 풀었던 문제와 거의 풀이가 유사하다. 다익스트라 알고리즘을 함수로 구현하고, 모든 노드에서부터의 다익스트라 함수를 모두 호출한 후, 반환되는 거리 리스트의 원소들의 총합을 한 리스트에 모은 후 가장 작은 값의 인덱스를 출력하도록 접근하였다. n
[ BOJ / Python ] 1238번 파티
이번 문제는 다익스트라 알고리즘을 활용하여 해결하였다. 이 문제에서는 다익스트라 알고리즘을 함수로 따로 구현해야 한다. 여러번 사용해야 하기 때문이다. 결과적으로 모든 마을에서의 다익스트라 함수를 호출해야 한다. x마을을 출발점으로 호출한 경우에는 모든 마을의 비용에
Graph Algorithm - Dijkstra's Algorithm
안녕하세요. 우원입니다.다익스트라 알고리즘에 대해 코드를 작성하고 분석하겠습니다.참고하시면 좋은 이전 포스트입니다.Graph Algorithm - DFS 바로가기Graph Algorithm - BFS 바로가기Graph Algorithm - MST 바로가기Graph Al