본문 바로가기

Dijstra2

[백준] - 1277. 발전소 설치 문제 풀이 1번 발전소부터 N번째 발전소까지의 최소 비용을 구하는 문제이기 때문에 다익스트라 알고리즘을 사용하여 해결하였다. 먼저 각 발전소의 좌표를 저장(plant)하고, 연결되어 있는지 여부를 저장(connected)하였다. 다음으로 다익스트라 알고리즘을 수행하기 전, 1번부터 각 정점까지의 거리를 나타내는 distance 배열을 연결된 경우에는 0, 연결되지 않은 경우에는 INF로 초기화해주었다. 다익스트라 알고리즘을 수행하면서 가중치를 더해주는 부분은 각 좌표간의 거리이기 떄문에 두 점 사이의 거리를 구하는 공식을 통해 구했다. 추가적으로 인접한 행렬에서 찾는 일반적인 경우와 달리 모든 발전소의 거리를 계속해서 갱신해 줄 필요가 있기 때문에 1~N까지 자기 자신을 제외하고 거리를 갱신해주었다. 풀.. 2021. 3. 24.

[개념 정리] 최단 거리 알고리즘 - 다익스트라 가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다. 두 정점 간의 최단 거리를 구하는 문제 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제 하나의 정점으로 가는 모든 최단 경로를 구하는 문제 정점 간의 모든 최단 경로를 구하는 문제 - 플로이드-와샬 저번 글에서는 4번 유형을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보았습니다. 이번 글에서는 2번 유형을 해결할 수 있는 다익스트라 알고리즘에 대해서 알아보겠습니다. 다익스트라 알고리즘은 간단하게 설명하면 시작 정점에서 거리가 최소인 정점을 선택해 .. 2021. 3. 22.

이전 1 다음

티스토리툴바