[코딩테스트 cheatsheet] 플로이드 워셜

개념

자주 나오는 유형은 아니지만 간간이 나오기 때문에 꼭 알고 있어야 된다고 생각한다.

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

 

언제 써야하는가?

모든 정점에서 모든 정점까지의 거리를 알고 싶을 때 쓴다.

 

시간복잡도가 O(n^3)으로 굉장히 느려 정점의 개수가 500이하일 경우에 고려해볼만 하다.

500 * 500 * 500 = 125,000,000 인데 500은 진짜 삐끗하면 시간초과가 날 가능성이 높다.

아예 플로이드 워셜을 의도로 하는 문제는 n이 100~200정도이다.

 

코드

# 처음은 graph를 큰 수로 초기화
INF = int(1e9)
graph = [[INF] * (n + 1) for _ in range(n + 1)]


# 자기자신에게 가는 경로가 0일 경우에만
for x in range(1, n + 1):
	graph[x][x] = 0


# 기본 플로이드 워셜
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])
            
            # 조금 더 빠르게 짜려면
            if graph[a][b] > graph[a][k] + graph[k][b]:
                graph[a][b] = graph[a][k] + graph[k][b]

 

 

백준 티어별로 살펴보는 문제 유형

플로이드워셜 유형의 문제가 많지는 않다.

실버 2

플로이드 워셜을 목적으로 낸 문제가 아닌 것 같다.

1058 - 친구 (https://www.acmicpc.net/problem/1058)

2- 친구가 되기 위해서는 두 사람이 친구거나, A와 친구이고 B와 친구인 C 가 존재해야한다.

이 말은 그래프에서 A -> B 로 갈 수 있거나, A -> C -> B 로 갈 수 있는 경로가 있으면 된다.

플로이드 워셜을 통해 이어져있는지 확인 가능하다.

---

실버 1

노드 간에 연결이 되어 있는지 알고 싶은 경우가 많은 것 같다.

1389 - 케빈 베이컨의 6단계 법칙 (https://www.acmicpc.net/problem/1389)

1058 문제와 비슷하게 사람간의 관계를 그래프로 이끌어내는지가 중요하다.

노드들이 거쳐서 연결되어 있는지, 경로의 길이는 어떻게 되는지를 묻는 문제다.

 

11403 - 경로 찾기 (https://www.acmicpc.net/problem/11403)

연결되어 있는 경로가 있는지 찾는 문제

---

골드 4

플로이드 워셜 알고리즘을 알고 있다면 바로 풀 수 있는 문제들이 나온다.

11404 - 플로이드 (https://www.acmicpc.net/problem/11404)

단순히 플로이드 워셜 알고리즘만 쓰면 풀리는 문제

주의점은 갈 수 없는 경로는 0으로 표시해야 한다는 것

 

14938 - 서강그라운드 (https://www.acmicpc.net/problem/14938)

다익스트라로 풀면 더 빠르지만 n이 100이기에 플로이드 워셜로 풀어도 무방한 문제

마지막에 아이템 처리를 해줘야 하지만 굉장히 간단함

역시 플로이드 워셜 알고리즘만 알고 있다면 쉽게 풀리는 문제

 

1956 - 운동 (https://www.acmicpc.net/problem/1956)

자기 자신 -> 다른 경로 -> 자기 자신으로 오는 싸이클을 찾아내는 것

그래프를 초기화할 때 자기자신 또한 INF 로 초기화하고 플로이드 워셜 알고리즘을 쓰면 싸이클이 구해진다.

 

2458 - 키 순서 (https://www.acmicpc.net/problem/2458)

나는 그래프를 3차원 배열로 표시해서 풀었으나 사실 2차원 배열로 풀 수 있다.

두 노드 (학생) 간의 키의 관계는 작거나, 크거나 두 가지이다. 1과 -1로 표현할 수 있다.

a -> k -> b 에서 a -> k 와 k -> b 가 같다면 a -> b 도 a -> k와 같다.

개인적으로는 골드 3에 가까운 것 같다.

---

골드 3

플로이드 워셜 알고리즘을 알고 살짝 응용할 수 있어야 한다.

1613 - 역사 (https://www.acmicpc.net/problem/1613)

플로이드 워셜을 살짝 응용한 문제, 2458번과 거의 같다.

거리는 관계 없이 3중 반복문을 통해 모든 노드들간의 관계를 살펴보는 문제다.

(a -> k -> b 에서 a -> k 와 k -> b 가 같다면 a -> b 도 a -> k와 같다)

처음에는 가까운 곳은 1, 먼 곳은 -1로 설정해서 풀었으나 python3 시간초과, pypy3 통과

graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) 의 형태는 간단하나 시간이 더 오래걸림

if 문으로 시간 단축해주는게 좋다.

---

골드 2

난이도가 어려워진다. 처음 보는 유형이라면 꽤 생각을 해야 풀 수 있는 문제가 나온다.

1507 - 궁금한 민호 (https://www.acmicpc.net/problem/1507)

플로이드 워셜 사용한 그래프를 복원하는 문제

이미 플로이드 워셜을 사용하여 최단거리를 구한 그래프를 입력값으로 준다. 이를 원래대로 복원하는 방법은 뭘까?

세 가지 경우로 나눠서 생각할 수 있다.

1. a -> k -> b 로 가는 길이와 a -> b 길이가 같다면

    => a -> k -> b 가 최단거리이거나  a -> k -> b 와 a -> b 가 같다는 것이다. a -> b 경로를 없애면 된다.

2. a -> k -> b 로 가는 길이가  a -> b 길이보다 작다면

    => 말이 안된다, 잘못된 경우이므로 -1 을 출력하면 된다.

3. a -> k -> b 로 가는 길이가  a -> b 길이보다 크다면

    => 길은 있긴 한데, 쓰지는 않은 경우이다.

 

11780 - 플로이드 2 (https://www.acmicpc.net/problem/11780)

주의할 점 : 같은 경로를 가진 버스가 있음, 입력값을 그래프에 저장할 때 최소값을 넣어주어야 한다.

플로이드 워셜이지만 거쳐간 모든 경로를 기록해주어야 하는 문제

---

골드 1

백준에서 골드 1의 플로이드 워셜 문제는 3문제 밖에 없다. 
골드 2와 골드 1이 비슷하다고 생각한다.
아마 골드2의 아이디어에서 한 발자국만 더 나아가야해서 골드 1인듯 하다.

2278 - 그래프 복원 (https://www.acmicpc.net/problem/2278)

플로이드 워셜 사용한 그래프를 복원하는 문제

1507번과 유사한 유형이다. 복원하고 나서 필요한 개수만큼 채워주면 된다.

---

플래티넘 5

어렵다..

13141 - Ignition (https://www.acmicpc.net/problem/13141)

노드를 잇는 가장 짧은 간선과 가장 긴 간선 정보를 모두 저장해야 한다.

짧은 간선을 기준으로 플로이드 워셜을 쓴다.

 

 

 

플로이드 워셜 문제풀 때 접근법

우선 정점의 개수가 500이하는 되어야 플로이드 워셜 알고리즘을 고려해볼 수 있다.

 

자기 자신으로 가는 거리가 0인가? 무한인가?

 

단순 플로이드 워셜 알고리즘을 아는지 물어보는 문제인가?

응용 해야한다면 어떤 부분을 해야하는가?

 

 

 

마지막 업데이트 : 2022.12.15