# dijkstra

154개의 포스트

[개념] 다익스트라 알고리즘(최단거리 알고리즘)

가장 짧은 경로를 찾는 알고리즘을 의미한다.문제상황한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현지점 간 연결된 도로는 그래프에서 간선으로 표현특정한 출발

3일 전
·
0개의 댓글
post-thumbnail

<Baekjoon> #4485 BFS, Dijkstra_녹색 옷 입은 애가 젤다지? c++

문제는 (0,0)에서 시작해 (N-1, N-1)까지 갈 때 최소 비용을 구하는 것처음에는 dp를 풀 때 외발뛰기, 삼각형 위의 최대 경로 같은 문제들을 생각하며 dp로 풀어야 하나 생각했지만 링크는 동서남북으로 움직일 수 있으며 그때마다 이미 구했던 최적의 해는 바뀔

2022년 5월 18일
·
0개의 댓글
post-thumbnail

[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

2022년 5월 8일
·
0개의 댓글

[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

2022년 5월 3일
·
0개의 댓글
post-thumbnail

[ BOJ / Python ] 10282번 해킹

이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 처음에는 백트레킹을 통해 경우의 수를 따져 구하려고 하였지만 다익스트라로 해결할 때에 훨씬 간단하게 해결할 수 있을 것이라는 생각을 중간에 하였고, 다익스트라로 거리를 체크하여 그 중 가장 큰 수를 걸리는 시간으로,

2022년 5월 2일
·
0개의 댓글

프로그래머스 배달

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시

2022년 4월 30일
·
0개의 댓글
post-thumbnail

[Algorithm] Shortest Path - 최단경로 알고리즘

최단 경로 알고리즘이란,최단 경로 알고리즘으로 주어진 노드와 간선들 중 가장 짧은 경로를 찾는 알고리즘최단 경로 문제의 종류하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제각 모든 정점에서 다른

2022년 4월 20일
·
0개의 댓글
post-thumbnail

<Baekjoon> #1753 Dijkstra_최단경로 c++

\[단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산우선 순위 큐에 지금까지 찾아낸 해당 정점까지의 최단 거리, 정점의 번호를쌍으로 넣음 priority_queue &lt;pair&lt;int, int>> pq; 정점까지의

2022년 3월 29일
·
0개의 댓글
post-thumbnail

[Python] 백준 11265 - 끝나지 않는 파티 문제 풀이

분류: Shortest Path (최단거리), Dijkstra(다익스트라), Floyd-Warshall(플로이드와샬)

2022년 3월 22일
·
0개의 댓글
post-thumbnail

[Python] 백준 1939 - 중량제한 문제 풀이

분류: Shortest Path (최단거리), Binary Search (이분탐색)

2022년 3월 15일
·
0개의 댓글
post-thumbnail

[ BOJ / Python ] 14938번 서강그라운드

이번 문제는 플로이드-와샬 알고리즘과 다익스트라 알고리즘을 사용하여 두번 풀어보았다. 우선 플로이드-와샬 알고리즘 풀이는 모든 정점에서 모든 정점으로의 최단 거리를 구하여 저장한 후에, 결과값들을 순회하며 최단 거리가 m 이하인 정점에 대한 아이템 수를 더하여 그 중

2022년 3월 12일
·
0개의 댓글
post-thumbnail

백준 13549, 숨바꼭질 3 - 다익스트라 / BFS

https&#x3A;//www.acmicpc.net/problem/13549목표 지점을 찾으면 탐색을 종료하는, 일반적인 DFS, BFS는 간선의 가중치가 모두 같아야 함.하지만, 본 문제는 +1, -1 로 가는 경우 가중치가 1,x2 로 가는 경우 가중치가 0 으로

2022년 3월 10일
·
0개의 댓글
post-thumbnail

백준 2665, 미로 만들기 - 다익스트라

https&#x3A;//www.acmicpc.net/problem/2665단순히 시작 지점 \[0]\[0] -> 끝 지점 \[n-1]\[n-1]으로의 최단경로는 BFS로 해결 가능.하지만, 방을 바꾸는 최소 개수에 해당하는 경로는 최단경로가 아닐 수 있음시작 지점으로부

2022년 3월 9일
·
0개의 댓글
post-thumbnail

백준 1504, 특정한 최단경로 - 다익스트라

https&#x3A;//www.acmicpc.net/problem/1504case 1) 1번 노드 -> v1 노드 -> v2 노드 -> n번 노드1번 노드 -> v1 노드 최단경로 다익스트라v1 노드 -> v2 노드 최단경로 다익스트라v2 노드 -> n번 노드 최단경로

2022년 3월 8일
·
0개의 댓글
post-thumbnail

백준 1753, 최단경로 - 다익스트라

https&#x3A;//www.acmicpc.net/problem/1753다익스트라한 노드 -> 다른 모든 노드로의 최단거리음이 아닌 간선의 가중치1) 비용 배열, 우선순위 큐 초기화dist\[]: 시작 노드 거리 0, 나머지 노드 무한대pq: (시작 노드, 0) 추가

2022년 3월 8일
·
0개의 댓글
post-thumbnail

[ BOJ / Python ] 1261번 알고스팟

이번 문제는 다익스트라 알고리즘을 통해 쉽게 해결하였다. 기존의 다익스트라 알고리즘 문제와 똑같이 작성을 하고, 힙에 넣을 다음 탐색 구역이 1일 경우에는 비용을 1 증가시켜주고, 그 외에는 비용을 그대로 유지한 상태로 진행시킨다. 이렇게 하면 목적지의 최소 비용을 구

2022년 3월 4일
·
0개의 댓글
post-thumbnail

[BOJ] 4485 - 녹색 옷 입은 애가 젤다지?

https&#x3A;//www.acmicpc.net/problem/4485젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!젤다의 전설 시리즈의 주인공

2022년 3월 3일
·
0개의 댓글
post-thumbnail

[ BOJ / Python ] 1389번 케빈 베이컨의 6단계 법칙

이번 문제는 바로 이전에 풀었던 문제와 거의 풀이가 유사하다. 다익스트라 알고리즘을 함수로 구현하고, 모든 노드에서부터의 다익스트라 함수를 모두 호출한 후, 반환되는 거리 리스트의 원소들의 총합을 한 리스트에 모은 후 가장 작은 값의 인덱스를 출력하도록 접근하였다. n

2022년 3월 2일
·
0개의 댓글
post-thumbnail

[ BOJ / Python ] 1238번 파티

이번 문제는 다익스트라 알고리즘을 활용하여 해결하였다. 이 문제에서는 다익스트라 알고리즘을 함수로 따로 구현해야 한다. 여러번 사용해야 하기 때문이다. 결과적으로 모든 마을에서의 다익스트라 함수를 호출해야 한다. x마을을 출발점으로 호출한 경우에는 모든 마을의 비용에

2022년 3월 2일
·
0개의 댓글

Graph Algorithm - Dijkstra's Algorithm

안녕하세요. 우원입니다.다익스트라 알고리즘에 대해 코드를 작성하고 분석하겠습니다.참고하시면 좋은 이전 포스트입니다.Graph Algorithm - DFS 바로가기Graph Algorithm - BFS 바로가기Graph Algorithm - MST 바로가기Graph Al

2022년 3월 2일
·
0개의 댓글