맛있는감귤

개요그래프/트리 탐색 알고리즘. 게임에서 많이 사용되는 최단거리 길찾기 알고리즘이다.다익스트라 확장판. BFS의 가지치기 알고리즘이라 생각하면 된다. 핵심 개념 1. 최소가 되는 지점을 우선 탐색 (우선 순위 큐)2. 휴리스틱 추정값 사용3. Open List / Closed List를 이용하여 노드 관리 다른 알고리즘과 차이점BFS (Breadth First Search) : 완전 탐색 알고리즘. 우선순위없이 모든 노드를 탐색한다. 다익스트라 : 일반적인 최단거리 알고리즘. 한 노드를 기준으로 모든 노드의 최단 경로를 찾기 때문에 시간 비용이 많이 든다.플로이드 : 모든 노드의 최단 경로를 찾는 알고리즘. 일반적인 시간 복잡도 O(N^3). 개념 설명1. 휴리스틱 추정값 f(x) = h(x) + g(x..

문제 : https://www.acmicpc.net/problem/11657최단거리를 찾는 문제같은데 타임머신이 있거나 시간을 역행하는 문제, 음수 가중치가 존재하는 대다수의 문제는 벨만-포드 알고리즘으로 해결가능합니다.다익스트라 알고리즘 같은 경우 해당 노드에 존재하는 간선을 보고 가중치가 가장 작은 값을 선택하게 됩니다.그렇기 때문에A -> B -> C / A -> C 의 루트에서1 5 -4 1 3의 값을 가질 때 노드 A의 간선의 가중치 5와 3만을 비교하기 때문에 원하는 답을 도출할 수 없습니다.왜냐하면 1 -> 5 -> -4이 더 최단 거리가 되기 때문이죠.그렇기 때문에 간선을 비교하고 또 노드의 개수-1만큼 또 비교를 해주면 됩니다. (도착지 노드까지 가는 간선은 전체 노드개수를 넘지 않기 때..