다익스트라 X BOJ_4485_녹색옷입은애가 젤다지?

시작 다익스트라 개념에 대해 정리한것을 포스팅 합니다. 다익스트라는 기본적으로 최단 경로로 많이들 알고 있지만, 최단 경로는 BFS 로도 접근할 수 있기 때문에 여기서 최소 비용 개념을 추가해주어야 합니다. 즉, 다이스트라는 최단 거리 + 최소 비용의 문제입니다. 조건 보통의 다익스트라의 문제 경우 아래 조건들을 만족합니다. 1. 방향 그래프 입니다. 2. 0 이상의 가중치 값을 가지고 있습니다 3. 사이클이 존재하지 않아야 합니다. 구현 (코드X) 다익스트라의 경우 BFS 개념에 그리디 알고리즘을 적용합니다. 덧붙이면, 최단 거리를 구하게 되지만 매 순간 가장 좋은 가중치 값을 선택하게 됩니다. 거리, 방문 여부 변수를 두어 다익스트라 알고리즘이 어떻게 동작하는지 살펴보겠습니다. 그림 처음 워크플로우는..