다익스트라

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라 정말 기본적인 다익스트라 문제! 따로 키 리스트를 설정하지 않아도 쉽게 풀 수 있다. 💻소스 코드 import sys import heapq input = sys.stdin.readline def dijkstra(s, e): pq = [] heapq.heappush(pq, (0, s)) # 출발지로 가는데 0원의 비용 visited = [0] * (N + 1) while pq: cost, w = heapq.heappop(pq) if w == e: return cost if visited[w]: continue visited[w] = 1 for newt_w, next_cost in adj[w]: if not visited[newt_w]: heapq.heappush(pq, (..

[python] 백준 - 1261. 알고스팟

🤔문제 해결 G4 | 다익스트라(BFS도 가능) 다익스트라 유형으로 되어있지만 BFS도 가능한거 같다. BFS로 풀 면 길을 찾아 갈 때 0이면 그냥 가고 1이면 +1해서 가면 된다. 이 문제는 다익스트라로 풀어봤다. ( 다익스트라와 우선순위큐(힙큐)는 짝꿍 ) 주어진 미로와 같은 크기의 2차원 배열을 만든다. ( 가중치를 업데이트 해줄 배열 ) 0,0 부터 주변을 탐색하며 방(0)이면 비용을 현재비용으로 넣고, 벽(1)이면 비용을 현재비용 +1해서 업데이트 해준다. 업데이트가 된 지점을들 힙큐에 넣고 목적지가 나올 때 까지 위의 과정을 반복한다. 💻소스 코드 import heapq if __name__ == '__main__': N, M = map(int, input().split()) # 문제는 1부..

다익스트라(dijkstra)

📔 다익스트라(dijkstra) 란 다익스트라를 들어가기 전에... 최단 경로란 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 간선의 가중치가 균일(1)할 경우 BFS를 사용 음의 가중치를 허용하지 않음 하나의 시작 정점에서 끝 정점까지의 최단경로 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 시작 정점(s) 에서 끝 정점(t) 까지의 최단 경로에 정점 x 가 존재한다. 이때, 최단 경로는 s 에서 x 까지의 최단경로와 x 에서 t 까지의 최단경로로 구성된다. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다. 아래 코드의 경우 시간복잡도는 O(N^2) 이다. 만약 우선순위큐를 이용하게 된다면 O(NlogN..

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라, 그래프 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 알고리즘 간선, 최소 등등 말이 나오면 다익스트라? 나의 경우 다익스트라를 풀 때 항상 우선순위 큐를 이용한다. (파이썬의 힙큐를 사용) A 에서 갈 수 있는 모든 정점들의 최소비용을 리스트에 담아두고 B 지점을 답으로 출력한다. 먼저 (가중치, 시작점)을 힙큐에 넣고 시작한다. 시작점에서 각 정점까지의 비용은 가장 큰 값(파이썬에서 float('inf')를 넣어두고 시작한다.) 힙큐에서 값을 하나씩 꺼낸다. 꺼낸 정점에서 이웃한 정점들 중에서 아직 방문하지 않았고, 이웃한 정점까지의 비용보다 현재비용 + 꺼낸 정점에서 이웃한 정점까지의 간선비용이 작으면 각 정점까지의 비용을 현재비용 + 꺼낸 정점에서 이웃한..

[python] 백준 - 1753. 최단경로

문제 해결 1. 방향이 있는 그래프에서 최단거리를 구하는 문제 | 보통 다익스트라 알고리즘을 사용한다. 2. 인접리스트, 가중치 배열, 힙큐를 준비한다. (1) 인접행렬보다 인접리스트가 조금 더 빠르다(?) (2) 가중치 배열: 인덱스 번호에 도착할 때의 가중치를 항상 최솟값으로 업데이트 해준다. (3) 힙큐는 항상 최솟값을 리턴해준다. 3. ex)a - c 와 a- c 로 갈 때의 가중치를 항상 비교하여 최솟값을 넣어줘야 한다. -> selected배열(출발했었는지 확인)을 만들어서 했는데 어짜피 단방향이라 필요가 없었다. python으로 제출 시 시간초과가 나서 pypy로 제출했더니 통과 했다. python으로 통과한 사람과의 코드를 비교해봤는데 차이가없었다..... 후😭 왜때문인지 모르겠다. 소스 ..