백준) 11403 경로찾기 - Python, 플로이드워셜

💭 나의 접근 방법

---

문제대로 접근하면 i행 j열에 1이면 j행을 찾아보는 방법으로 진행하려고 했다. 그래서 DFS방식이거나 BFS방식으로 생각해 볼 수 있다.

이 문제는 플로이드워셜로 풀 수 있다. 플로이드 워셜은 최단경로 문제에서 사용되는 방식으로 3중 반복문으로 사용된다.

 

$$ D_{ab} = min(D_{ab},D_{ak}+D_{kb}) $$

 

a→b 와 a→k,k→b 를 비교 후 더 작은 값으로 갱신하는 방법으로 O(N^3) 시간복잡도를 가질 수 있기 때문에 노드의 개수가 적을 경우 (500개 이하일 경우)에 사용하는 것이 효율적이다.

 

이 문제에서는 최솟값으로 갱신하는것이 아닌 지나가는 경로를 모두 파악하는 것이므로 지나간 경우 1로 표시해 주면 된다.

 

 

💡 결과

---

# 11403 경로 찾기 S1

# # 1. BFS 방법
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
graph = [list(map(int,input().split())) for _ in range(N)]
result = [[0]*N for _ in range(N)]

def bfs(x):
    q = deque()
    q.append(x)
    check = [0 for _ in range(N)]
    while q:
        y = q.popleft()
        for i in range(N):
            if check[i] == 0 and graph[y][i] == 1:
                q.append(i)
                check[i] = 1
                result[x][i] = 1

for i in range(N):
    bfs(i)
for i in result:
    print(*i)

# 2. DFS 방법
import sys
input = sys.stdin.readline

N = int(input())
graph = [list(map(int,input().split())) for _ in range(N)]
result = [0 for _ in range(N)]
def dfs(x):
    for i in range(N):
        if graph[x][i] == 1 and result[i] == 0:
            result[i] = 1
            dfs(i)

for i in range(N):
    dfs(i) #각 행마다 갈수 있는곳 다 탐색
    for j in range(N):
        if result[j] == 1:
            print(1,end=' ')
        else:
            print(0,end=' ')
    print()
    result = [0 for _ in range(N)]

# 플로이드 워셜
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][k] and graph[k][j]:
                graph[i][j] = 1
    
for g in graph:
    print(*g)

 

 

 

💫 느낀점

---

최단경로문제에서 플로이드와셜을 또 마추칠일이 있다. 따라서 최단경로를 따라서 정리하면 좋을것 같다.

 

 

 

 

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

11403번: 경로 찾기