플로이드와샬

플로이드 와샬(Floyd Warshall)

📔 플로이드 와샬(Floyd Warshall) 란 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. ( 출처: 위키백과 ) 모든 정점에서 모든 정점으로의 최단 경로를 구하는 것! 거쳐가는 정점을 기준으로 구한다. 다이나믹 프로그래밍 기법을 이용 다익스트라의 경우 한 정점에서 모든 정점까지 의 최단 경로 반복문이 3개이므로 시간복잡도는 O(N^3) 이다. 하지만 코드는 매우 간단하다. 📔 플..

[python] 백준 - 2606. 바이러스

문제 해결 1. 플로이드와샬 알고리즘 - 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 2. 라고 되어있지만 사실 잘 모르겠고, 이어져있는 정점들을 모두 찾는 문제이다. 3. 인접리스트를 만들고, BFS로 이어져있는 모든 정점을 찾으면 해결되는 간단한 문제! 소스 코드 from _collections import deque def bfs(vertex): # 속도가 빠른 디큐를 사용해서 BFS 탐색 q = deque() q.append(vertex) # 시작점 방문 체크를 True로 해준다음 visit[vertex] = True while q: # 큐에 쌓인 노드들 중에서 하나를 꺼내고 current = q.popleft() # 노드에 인접한 이웃들중 for neighbor in adj[current]..