플로이드 워셜 문제 유형

Chooooo·2023년 2월 15일

문제 유형 플로이드 워셜

알고리즘 활용하는 문제 유형들

목록 보기

21/33

플로이드 워셜 알고리즘 개요

⚽ 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.

⚽ 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.

다만 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다.

⚽ 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.

⚽ 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.

⚽ 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.

a에서 b로 가는 최단 거리 .

🏈 점화식 : dis(a,b) = min(dis(a,b), dis(a,k) + dis(k,b))

😎 플로이드 워셜 알고리즘은 최단거리를 저장할 2차원 리스트 하나만 챙긴다고 생각하면 된다.

⚽ 플로이드 워셜 알고리즘 동작 과정 살펴보기

🚀 초기 상태 : 그래프를 준비하고 최단거리 테이블을 초기화한다.

🚀 [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

🚀 [Step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한.

🚀 [Step 3] 3번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

🚀 [Step 4] 4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

플로이드 워셜 알고리즘 코드

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
# 이 3중 포문이 바로 플로이드 워셜 알고리즘 !!
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == 1e9:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()

다시 코드 작성해봄

n = int(input())
m = int(input())
# 노드의 개수 및 간선의 개수 입력받기
# 2차원 리스트(그래프 표현)을 만들고, 모든 값을 무한으로 초기화
INF = int(1e9) # 1억
g = [[INF] * (n+1) for _ in range(n+1)] # 1번 인덱스부터 사용하기 위해

# 자기 자신으로 가는 비용은 0으로 초기화
for i in range(1,n+1):
    g[i][i] = 0 # 자기 자신으로 가는 비용 0으로

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    # a에서 b로 가는 비용을 c로 초기화
    a,b,c = map(int, input().split())
    g[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            g[a][b] = min(g[a][b], g[a][k] + g[k][b])

# 수행된 결과를 출력
for a in range(1,n+1):
    for b in range(1,n+1):
        # 도달할 수 없는 경우 무한이라고 출력
        if g[a][b] == INF:
            print("도달 못함.")
        else: # 도달할 수 있는 경우 거리를 출력
            print(g[a][b], end = " ")
    print()

알고리즘 분석

문제를 보며 확인하자

위 3중 포문이 플로이드-워셜 알고리즘의 핵심 !!!

플로이드 워샬 알고리즘

N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에는 도시의 수N(N<=100)과 도로수 M(M<=200)가 주어지고, M줄에 걸쳐 도로정보와 비용(20 이하의 자연수)이 주어진다. 만약 1번 도시와 2번도시가 연결되고 그 비용이 13이면 “1 2 13”으로 주어진다.

▣ 출력설명
모든 도시에서 모든 도시로 이동하는데 드는 최소 비용을 아래와 같이 출력한다.
자기자신으로 가는 비용은 0입니다. i번 정점에서 j번 정점으로 갈 수 없을 때는 비용을 “M"으로 출력합니다.

▣ 입력예제 1
5 8
1 2 6
1 3 3
3 2 2
2 4 1
2 5 13
3 4 5
4 2 3
4 5 7

▣ 출력예제 1
0 5 3 6 13 //1번 정점에서 2번정점으로 5, 1에서 3번 정점으로 3, 1에서 4번 정점으로 6......
M 0 M 1 8 //2번 정점에서 1번 정점으로는 갈수 없으므로 “M", .......
M 2 0 3 10
M 3 M 0 7
M M M M 0

그래프에서 모든 정점에서 모든 정점으로 가는 최단거리. 그 최소 비용을 구하는 것이다.

1번 정점에서 다른 정점들로 가는 최단거리를 구하고, 또 2번 정점에서 다른 정점들고 가는 최단거리 구하고, 등등 끝까지 도는 것이다.
이렇게 생각하면 플로이드 워셜의 dp 테이블은 2차원 리스트이다.

🚀 플로이드 워셜도 냅색 알고리즘과 동일한 원리이다.

😀 dis[i][j]는 i정점에서 j정점으로 가는데 드는 최소비용 값을 저장한다. (i가 출발 정점, j가 도착 정점)

일단 dp테이블에 한번의 간선으로 갈 수 있는 값들(직관적. 자명하게 알 수 있는 값)을 미리 초기화 하고 진행하자. (즉 이 값들이 인접행렬 초기값이야)
처음 dp 테이블에 저장된 값들은 한번에 갈 수 있는 값들만 저장되어 있는 것이다.

🚀 이제 기존 값(i → j로 가는 기존 값)과 중간에 노드를 거쳐서(몇개를 거치든) 가는 값 중에 최소 값을 택할 것이다.

i → j로 갈 때 1~N까지의 노드가 몇개든 존재할 수 있다.
이 사이에 존재하는 노드들은 1,2,3이 꼭 있다면 1→2→3 순이 아니라 2→1→3 처럼 될 수도 있다.

🏈 위 내용을 이해하는 것이 매우 중요한데, 예를 들어 k == 3을 적용하고 있는 2중 포문을 돌고 있다고 생각하면 dis[5][4]의 값은 (dis[5][3] + dis[3][4]) 이렇게 가는 방법이 존재할 수도 있다.

k가 3을 적용하고 있다는 것은 dp 테이블이 k = 1,2를 거쳐서 가는 것까지 적용된 테이블 값일거야. 그렇다면 dis[5][3]의 값이 5 → 2 → 3으로 가는 값이 최단거리 일 수 있고, dis[3][4]의 값은 3 → 1 → 4의 값이 최단거리 일 수도 있다.
그렇다면 dis[5][4]의 값은 5 → 2 → 3 → 1 → 4 순으로 가는 것이 최단거리라는 것인데, k는 이미 1,2를 거쳐왔고 k는 현재 3이다. 다시 말해 꼭 1→2→3순으로 되는 것이 아니라는 거야!
결국 전체를 다 돌면 모든 노드에서 모든 노드까지의 최단거리를 다 알 수 있게 된다는 뜻 !

😀 다시 풀어본 코드

n,m = map(int, input().split())
INF = int(1e9)
g = [[INF] * (n+1) for _ in range(n+1)]
for i in range(1,n+1):
    g[i][i] = 0 # 본인으로 가는 것은 0

for _ in range(m): # 정보
    a,b,c = map(int, input().split())
    g[a][b] = c  # a->b 비용 c

# 플로이드 워셜 알고리즘
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            g[a][b] = min(g[a][b], g[a][k] + g[k][b])

for a in range(1,n+1):
    for b in range(1,n+1):
        if g[a][b] == INF:
            print("M", end = " ")
        else:
            print(g[a][b], end = " ")
    print()

플로이드 워셜 알고리즘 활용 문제

회장뽑기(플로이드-워샬 응용)

월드컵축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이모임은 만들어진지 얼마 되지 않았기 때문에 회원사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 서로 모두 알 수 있다.
각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.
예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나, 친구의 친구임을 말한다. 또한, 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친국의 친구의 친구임을 말한다.4점, 5점등은 같은 방법으로 정해진다.
각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구 사이이면서 동시에 친구의 친구사이이면, 이 두 사람은 친구사이라고 본다. 회장은 회원들 중에서 점수가 가장 작은 사람이 된다.
회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

▣ 입력설명
입력의 첫째 줄에는 회원의 수가 있다.
단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 번호가 붙어있다. 마지막 줄에는 -1이 두 개 들어있다

▣ 출력설명
첫째 줄은 회장 후보의 점수와 회장후보 수를 출력하고 두 번째 줄은 회장 후보를 모두 출력한다.

▣ 입력예제 1
5
1 2
2 3
3 4
4 5
2 4
5 3
-1 -1

▣ 출력예제 1
2 3
2 3 4

import sys
sys.stdin = open("input.text", "rt")
# input = sys.stdin.readline

#가까운 정도
n = int(input())
INF = 2424242424
dis = [[INF] * (n+1) for _ in range(n+1)]
for i in range(1,n+1):
    dis[i][i] = 0

while True:
    a,b = map(int, input().split()) #친구 사이
    if a == -1 and b == -1: 
        break
    dis[a][b] = 1
    dis[b][a] = 1

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
#여기까지 플로이드 워셜을 수행하면 각 회원들의 가까움 정도를 확인할 수 있다. (모든 노드에서 모든 노드까지의 최단거리 구함)


res = []
for i in range(1,n+1):
    temp = 0
    for j in range(1,n+1):
        if dis[i][j] > temp:
            temp = dis[i][j]
    res.append(temp)


score = min(res) #회장의 점수
cnt = res.count(score) #회장 점수를 가진 사람 수
print(score, cnt)
for i in range(len(res)):
    if res[i] == score:
        print(i+1, end = " ")