다익스트라

https://0422.tistory.com/104 1967 백준 파이썬 이 문제를 풀려면 어떤 임의의 점에서 가장 많이 떨어진 점은 지름의 한 점에 해당한다는 점을 알고 있어야 한다. 그림을 통해 보면 원 내부의 직선에서 어떤 점을 잡든, 그 점에서 가장 먼 점은 0422.tistory.com 이전 게시글과 거의 똑같은 유형의 문제. 해설은 전 게시글과 동일하기에 쓰지 않겠다. 다만, 차이점은 이전 문제는 BFS로 해결했다면, 이번 문제는 다익스트라로 해결했다. import heapq INF=int(1e9) def dik(start): heap=[] distance=[INF for _ in range(n+1)] distance[start]=0 heapq.heappush(heap,(start,0)) wh..

별거 없는 다익스트라 문제. 하는김에 다익스트라를 복습해 보자. 다익스트라는 시작점으로부터 어떤 도착점 까지의 최단 거리를 구하는 알고리즘이다. 그래서 g라는 리스트에 가는데 걸리는 (시간,목적지)를 저장한다. 그리고 다익스트라 함수안에서 distance라는 리스트를 만든다. 여기에다가 최단 거리를 갱신해 줄 것이다. 최단거리를 갱신해야 하므로 int(1e9)로 선언한다. 그 후에 힙을 만들어서 cost와 start를 넣어준다. 그리고 힙에 저장된 것이 없을 때 까지 cost, now를 꺼내어서 비교한다. 이때, 저장된 cost가 distance[now]보다 크면 더이상 볼 필요가 없으므로 넘어간다. 그렇지 않다면, g[now]에 있는 리스트들을 반복시킨다. g[now]는 cost와 목적지로 저장되어 있..

다익스트라 알고리즘에 대한 정확한 이해가 없어서 어려웠던 문제. 이 문제를 통해서 개념을 확실히 익혔다. 다익스트라는 dfs와 비슷한 방식으로 작동한다. 최단 경로는 최단 경로의 합이라는 알고리즘으로 작동한다. 따라서 힙을 통해 구현할 수 있다. 약간 조건이 잔뜩붙은 dfs같은 느낌이다. 시작점에서 최단경로를 찾는다 -> 최단경로를 힙에 넣는다 -> 최단경로를 꺼내어 시작점과 중간 경로까지의 값과 비교한 후에 최단 경로가 더 짧은 경우에만 더 진행한다.(이걸로 시간초과가 갈린다.) -> 현재 저장된 중간경로에서 또 다른 경유 지점까지의 합이 저장된 거리보다 짧을 경우, 저장된 거리를 갱신한다. -> 저장된 거리를 힙에 다시 넣는다. 그리고 이 문제의 경우, 특정한 경로를 지나야 하는데 그 발상을 떠올리지..