[백준] 플로이드 워셜(Floyd-Warshall) 알고리즘 11403번

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

2차원 그래프에서

각 노드끼리 서로 갈 수 있는 경로가 있는 지 확인하는 문제

i에서 j로 가는 간선이 존재하는가 - 1

존재하지 않는가 - 0

---

1. BFS를 이용하여 구현

# BOJ_11403
from collections import deque
import sys
input = sys.stdin.readline


def bfs(start, end):
    q = deque()
    visited = [[False] * n for _ in range(n)]
    for j in range(n):
        if graph[start][j] == 1:
            q.append((start, j))
    while q:
        # print(q)
        a, b = q.popleft()
        if visited[a][b]:
            continue
        visited[a][b] = True
        # print('(a, b) =', a, b)
        if b == end:
            return 1
        for i in range(n):
            if graph[b][i] == 1:
                q.append((b, i))
    return 0


# 입력
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
for x in range(n):
    for y in range(n):
        # print('x, y = ', x, y)
        # print(bfs(x, y))
        print(bfs(x, y), end=' ')
    print()

---

2. 플로이드 워셜 알고리즘으로 구현

# BOJ_11403_Floyd_Warshall
import sys
input = sys.stdin.readline


# 입력
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]


# 플로이드-워셜 알고리즘
for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1 or (graph[i][k] == 1 and graph[k][j] == 1):
                graph[i][j] = 1

# 출력
for row in graph:
    for col in row:
        print(col, end=' ')
    print()

위가 플로이드 워셜 알고리즘으로 푼 것

플로이드-워셜로 푼 알고리즘로 푼 게 확실히 160ms로 BFS로 구현한 코드 실행 시간인 1508ms 보다 짧았다.

두 코드 모두 O(N^3)인데, 플로이드-워셜의 시간이 약 10배 정도 짧음을 알 수 있었다.

다익스트라 알고리즘 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우

플로이드 워셜 알고리즘 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우