다익스트라
-
코딩 테스트 - 다익스트라(Dijkstra)의 개념과 문제Coding Test/Coding Test 문제 추천 2021. 9. 26. 14:29
다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘이란? ㆍ 그래프 상의 한 노드에서 다른 모든 노드까지의 최단 거리를 구할 때 유용하게 사용되는 알고리즘이다. ㆍ 노드와 노드 사이의 간선의 가중치가 0 이상의 정수일 때만 사용이 가능하다. 다익스트라 문제 난이도(하) ㆍ 백준 1753번 : 최단경로 (🥇 골드 5 티어) ㆍ 백준 1916번 : 최소비용 구하기 (🥇 골드 5 티어) ㆍ 백준 5972번 : 택배 배송 (🥇 골드 5 티어) ㆍ 백준 14284번 : 간선 이어가기 2 (🥇 골드 5 티어) 난이도(중) ㆍ 백준 1446번 : 지름길 (🥈 실버 1 티어) ㆍ 백준 1504번 : 특정한 최단 경로 (🥇 골드 4 티어) ㆍ 백준 1238번 : 파티 (🥇 골드 3 티어) ㆍ 백준 17396번 : ..
-
다익스트라 알고리즘(Dijkstra Algorithm)Computer Science/Algorithm 2021. 9. 25. 18:38
다익스트라 알고리즘이란? - 그래프 상의 한 노드에서 다른 모든 노드까지의 최단 거리를 구할 때 유용하게 사용되는 알고리즘이다. - 노드와 노드 사이의 간선의 가중치가 0 이상의 정수일 때만 사용이 가능하다. 다익스트라 알고리즘의 동작 과정 1단계 노드 1 2 3 4 5 6 거리 0 2 5 1 INF INF - 출발 노드인 1을 기준으로 인접한 노드인 2, 3, 4 노드에 대한 최단 거리 테이블을 만들어 준다. - 인접하지 않은 노드인 경우 무한으로 표시한다. 2단계 노드 1 2 3 4 5 6 거리 0 2 1+3=4 1 1+1=2 INF - 노드 1과 인접한 노드들 중 최단 거리가 가장 짧은 노드인 4번으로 진행한다. - 노드 4와 인접한 노드는 3, 5 노드이고, 이 노드까지의 최단 거리와 기존의 최단..