# dijkstra

160개의 포스트
post-thumbnail

[Baekjoon] 백준 9370 미확인 도착지 - c++

해당 문제를 풀면서 많은 어려움을 겪었다.. 오랜만에 다익스트라 알고리즘을 구현하는데 애먹었다. 다익스트라 알고리즘은 시작정점에서 이동가능한 정점까지 거리를 체크하고 체크한 값중 가장 작은 값인 정점에서 또 이동가능한 정점까지 거리를 체크해 나가는 방식이다. 구현할때

2022년 6월 29일
·
0개의 댓글

[Algorithm] 다익스트라 vs 벨만포드 vs 플로이드와샬

그래프에서 하나의 노드에서 다른 모든 노드로 이동하는 최단 비용을 구하는 알고리즘시작 노드의 비용을 0 으로 초기화 (본인에게 이동하는 비용은 0)우선 순위 큐에 시작 노드를 삽입 (연결 리스트로 구현하는 등 다른 방법도 있는 듯 하다)큐가 비어있을 때 까지 아래의 동

2022년 6월 19일
·
0개의 댓글

[13549번] 숨바꼭질 3

백준 13549번 숨바꼭질 3본 문제는 다익스트라 알고리즘을 이용하면 문제를 해결할 수 있습니다.그래프 문제에서 시작 노드에서 도착 노드가 이어져 있다는 것을 응용해서 해당 문제는 특정 칸에서 갈 수 있는 경우의 수를 3가지(+1, -1, X2)로 보면 됩니다.

2022년 6월 7일
·
0개의 댓글

[1753번] 최단경로

백준 1753번 최단경로힙 자료구조를 이용해 다익스트라 알고리즘으로 문제를 해결할 수 있습니다.우선순위가 높은(거리가 가장 짧은) 노드를 힙에서 뽑아내 최단거리를 갱신합니다.

2022년 6월 7일
·
0개의 댓글

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

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

2022년 5월 22일
·
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개의 댓글

[오답노트] 백준 #1238 파티 (파이썬)

그래프 간선 방향을 역으로 바꾸면 생기는 일

2022년 5월 2일
·
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개의 댓글

백준 #11779 최소비용 구하기 2 (파이썬)

아주 전형적인 다익스트라 문제다. 하지만 최단 비용만 출력하는 게 아니라 그때의 경로를 함께 출력해야 하므로 추가 변수가 필요하다.

2022년 4월 6일
·
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개의 댓글