[백준] 11403 경로찾기 (python 파이썬)

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

11403번: 경로 찾기

---

아이디어

1. 플로이드 와샬

• 예전에 가중치가 있는 플로이드 와샬을 푼 경험이 있어서 이번에는 간단하게 해결했다.
• 기존 알고리즘에서 약간만 변형하면 됨

---

코드 설명

for k in range(N):
    for i in range(N):
        for j in range(N):
            if adj_matrix[i][k] == 1 and adj_matrix[k][j] == 1:
                adj_matrix[i][j] = 1

k는 거쳐가는 노드, i는 시작 노드, j는 도착 노드 순으로 반복문을 작성하고, 

i -> k와 k -> j가 존재하면 i -> j로 이어주는 작업을 하면 된다.

 

코드는 간단하지만 플로이드 알고리즘에서 삼중 for문의 순서는 중요하다. 

 

예를 들어 1 -> 3 -> 2 -> 5 연결되어있다고 생각해보자.

거쳐가는 노드(k)가 가장 바깥에 있으면

k = 2 일 때 3 -> 2 -> 5를 이어서 3 -> 5로 연결하고

k = 3 일 때 1 -> 3 -> 5를 이어서 1 -> 5를 연결해준다.

 

그럼 시작 노드(i)가 바깥에 있다면 어떻게 될까?

먼저 i = 1 일 때 1 -> 2, 2-> 5를 먼저 검사하니까 연결이 안 된 상태로 넘어간다.

이후 1 -> 3, 3 -> 2 검사를 하면 이어지니까 1->2로 연결된다.

여기서 다시 1 -> 2와 2-> 5를 검사할 수 없다. 왜냐, 이미 반복문에서 지나갔기 때문이다.

그래서 다시 연결 검사 안 해줌.

 

말로 풀어서 생각해보면 시작이나 끝을 기준으로 먼저 연결하는 게 아니고

중간다리를 기준으로 미리미리 연결해둬야 나중에 따다닥 연결이 된다.

 

---

전체 코드

import sys
N = int(input())

adj_matrix = []
for _ in range(N):
    adj_matrix.append([int(x) for x in sys.stdin.readline().rstrip().split()])

for k in range(N):
    for i in range(N):
        for j in range(N):
            if adj_matrix[i][k] == 1 and adj_matrix[k][j] == 1:
                adj_matrix[i][j] = 1

for row in adj_matrix:
    print(' '.join(map(str,row)))