프로그래민👨‍💻

다익스트라를 활용한 문제였다. 총 2번의 다익스트라를 활용하였는데, 출발점 기준 그리고 친구 기준으로 두번 다익스트라를 활용하였다. 출발에서 목적지까지의 거리랑 출발에서 친구 + 친구에서 목적지 까지의 거리를 비교하는 간단한 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92..

다익스트라를 활용하는 문제였다. 최단 경로 문제이지만 이 문제는 N의 최대값이 1000이기에 플로이드와샬 기법보다는 다익스트라가 적합할 것 같아서 다익스트라로 접근하였다. 이 문제는 경로가 주어지고 특정 목적지를 왕복하는 문제였다. 따라서 두가지로 나누어 풀어보았다. 첫번째로 시작점에서 목적지까지의 다익스트라, 두번째로 목적지에서 시작점까지의 다익스트라, 이 두가지를 구하여 시작점을 바꿔가며 최대값을 확인하여 답을 풀었다. 즉 max(distanceFromStart[end] + distanceFromEnd[start]) 값을 구하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..

다익스트라를 활용하는 최단거리 문제이다. 문제를 맨처음 보았을 때 단순하게 백트래킹으로 모든 경로를 확인해보았다. 하지만 주어질 수 있는 동굴의 크기의 최대값이 125이기 때문에 시간초과가 발생하게 된다. 따라서 다익스트라를 활용해보았다. 다익스트라는 기본적으로 다음과 같은 원리로 동작한다. 출발 노드를 설정 최단 거리 테이블을 최대값으로 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 위 과정에서 3번 4번을 반복 그래프와 다르게 2차원 배열에서는 4방향을 갈수있다고 가정하고, 우선순위 큐를 이용하여 구현해보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..

최단경로를 구하는 문제이다. 이 문제에서 그래프의 가중치가 음을 가지지 않으므로 Dijkstra알고리즘을 사용하여 해결하였다. Dijkstra알고리즘은 Prim알고리즘 기법과 동일하지만 단한가지 차이점을 가진다. 그차이점은 단순 d값의 비교가 아니라 d[dest]와 weight+d[start]를 해주는 것이다. 즉, 단순거리가 아니라 누적거리를 비교해준다. 이렇게 되면 d배열에는 출발점에서 각 index까지의 최단 거리가 저장이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54..