🧚‍♂️알고리즘🧚‍♂️ - 그래프 - 플로이드 워셜

🧚‍♂️플로이드 - 워셜🧚‍♂️

모든 노드 간 최단 경로 탐색

(음수 가중치 있어도 가능)

(종적 계획법(DP) 원리 이용)

 

시간복잡도 : O(V^3)

노드 개수의 범위가 작아야 함.

(모든 노드부터 모든 노드까지의 최단거리 구하기 때문. 시작노드 하나부터 모든 노드까지의 최단 구하는 다익스트라/벨만포드 와는 다름)

 

 

최단 경로 위에 어떤 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로임.

=> 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합으로 이뤄진다.

->

점화식 : "S에서 E까지의 최단 거리" = Math.min("원래 S에서 E까지의 최단 거리",  "S에서 K까지의 최단 거리"+"K에서 E까지의 최단 거리")

 

! 중간다리(K,연결지점) 에 핵심이 있는 알고리즘

---

1. 리스트 선언하고 초기화하기

노드 S에서 E까지 가는 최단 거리를 저장할 리스트.

2차원으로 선언하고 s==e인 부분은 0으로!

 

2. 최단 거리 리스트에 그래프 데이터 저장하기

출발 노드가 S, 도착 노드가 E, 에지의 가중치가 W => D[S][E] = W

"인접 행렬"로 구현!

+ 두 노드를 잇는 에지가 여러 개면 그중 가중치가 작은 걸로 갱신하면 될 듯

 

3. 점화식으로 리스트 업데이트하기

for 중간지점 K마다 (노드개수만큼)

    for 출발노드 S마다 (노드개수만큼)

        for 도착노드 E마다 (노드개수만큼)

            점화식 수행 ( D[S][E] = Math.min(D[S][E],D[S][K]+D[K][E])

 

(O(노드개수^3))

---

🥇골드4 ( 정석 문제인 듯)

11404번: 플로이드

import sys
N = int(sys.stdin.readline()) # 노드
M = int(sys.stdin.readline()) # 에지

#인접 행렬 2차원 구현
distance = [[sys.maxsize for _ in range(N+1)] for _ in range(N+1)] #거리 리스트를 큰 값으로
for i in range(1,N+1):
    distance[i][i] = 0 # 자기 자신과의 거리 0

# 가중치 저장 (여러개 있을 시 작은 값으로 갱신)
for i in range(M):
    s,e,v = map(int,sys.stdin.readline().split())
    if distance[s][e] > v:
        distance[s][e] = v

#플로이드-워셜
for k in range(1, N+1):
    for s in range(1, N+1):
        for e in range(1, N+1):
            if distance[s][e] > distance[s][k]+distance[k][e]:
                distance[s][e] = distance[s][k]+distance[k][e] #점화식

#결과
for i in range(1,N+1):
    for j in range(1,N+1):
        if distance[i][j] == sys.maxsize:
            print(0,end=' ')
        else:
            print(distance[i][j],end=' ')
    print()

이해..이해를 제대로

왜 K가  먼저여야 하는가..?

???? k 순서 바꾸면 어떨 때는 정답이 나오고 어떨 때는 아니다. 왜지??????

---

🥈실버1 + 💠끼얏호 클래스 4 문제!

11403번: 경로 찾기

모든 노드 쌍에 대해 경로가 있는지 파악하는 문제

 

S 노드와 E 노드가 모든 중간 경로 중 1개라도 연결되어 있다면 S와 E는 연결 노드임.

distance[s][k] == 1 and distance[k][e] ==1 라면 distance[s][e] == 1

import sys
N = int(sys.stdin.readline()) 

distance = [] 
for i in range(N):
    nlist = list(map(int,sys.stdin.readline().split()))
    distance.append(nlist) 

#  변형 플로이드-워셜
for k in range(N):
    for s in range(N):
        for e in range(N):
            if distance[s][k] == 1 and distance[k][e]== 1:
                distance[s][e] = 1

#결과
for i in range(N):
    for j in range(N):
        print(distance[i][j],end=' ')
    print()

---

🥈실버1

1389번: 케빈 베이컨의 6단계 법칙

예전에 BFS로 풀엇나보다

import sys
N,M = map(int,sys.stdin.readline().split())

distance = [[sys.maxsize for _ in range(N+1)] for _ in range(N+1)] 
for i in range(1,N+1):
    distance[i][i] = 0 

for i in range(M):
    s,e = map(int,sys.stdin.readline().split())
    distance[s][e] = 1 
    distance[e][s] = 1 

#플로이드-워셜
for k in range(1, N+1):
    for s in range(1, N+1):
        for e in range(1, N+1):
            if distance[s][e] > distance[s][k]+distance[k][e]:
                distance[s][e] = distance[s][k]+distance[k][e] 


Min = sys.maxsize
Answer = -1

for i in range(1,N+1):
    tmp= 0
    for j in range(1,N+1):
        tmp += distance[i][j]
    if Min > tmp:
        Min = tmp
        Answer = i

print(Answer)

이건 플로이드 워셜로