공부공부/알고리즘!14 다익스트라, 플로이드와샬, 벨만포드에 대해서! 가중치가 있는 그래프탐색! 다익스트라 — 시작점과 다른 모든 정점간의 최단경로를 탐색할때 사용 시작점부터 탐색하여 연결되는 정점의 거리를 최솟값으로 최신화 해주고 시작정점으로 부터 연결된 정점까지의 거리중 최솟값을 가지고 아직 방문하지않은 정점으로 이동하여 반복해줍니다. # 방문하지 않은 노드이면서 시작노드와 최단거리인 노드 반환 def get_smallest_node(): min_value = INF index = 0 for i in range(1, n+1): if not visited[i] and distance[i] < min_value: min_value = distance[i] index = i return index def dijkstra(start): # 시작노드 방문처리 distance[s.. 2022. 3. 4. BFS,DFS에 대해서 간선의 가중치가 없는 그래프 탐색! BFS-너비탐색 최단거리를 구하는 문제에서 자주 사용 큐를 이용하여 구현 탐색할수록 메모리 업업 최단거리는 무조건 보장 def bfs(graph, start_node):# 너비 # 큐사용해서 한쪽으로는 하나씩 꺼내주고 다른쪽으로는 꺼낸값의 자식노드를 입력받는 형태로 구성 visit = list() queue = list() queue.append(start_node) while queue: node = queue.pop(0) if node not in visit: visit.append(node) queue.extend(graph[node]) return visit BFS를 사용하는 경우, 알고리즘 문제풀이 그래프 탐색(BFS, DFS)에 대한 알고리즘 문제풀이 우리가.. 2022. 3. 4. 이전 1 2 3 다음 728x90 반응형
