다익스트라

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

다익스트라를 적용할 때 맵에 값을 갱신할 필요가 있을 경우 상황은 다음과 같이 가정합니다. 맵이 존재하고 시작 위치에서 출발했을때 방향은 무관 각 맵마다 (점수,시간) 이 주어지고 한칸 움직일때마다 1초가 지난다고 가정 이럴 경우에 최대 점수는? 단, 방문했던 맵은 다시 방문가능 하지만 점수는 획득 불가, 시간이 초과한곳도 마찬가지로 점수 획득 불가. 코드 컨셉 : 백트래킹 최대 맵의 크기 : N 이라고 한다면 재귀함수 부분만 구성해보면 if(time>N){ answer = Math.max(answer,maxAnswer); return; } for(int i=0; itime && visit[ddx][ddy]== 0){ visit[ddx][ddy] = 1; answer += delivery[delivery..