[Python][백준/BOJ] 11403번 : 경로 찾기

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

11403번: 경로 찾기

 

내 코드

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

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] == 1 and graph[k][j] ==1) or graph[i][j]==1:
                graph[i][j]=1
                

for i in range(n):
    print(*graph[i])

 

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

플로이드 워셜 알고리즘 = 인접행렬

플로이드 워셜 알고리즘의 개념 자체가 인접행렬이다.

해당 문제가 플로이드 워셜 문제인지 알 수 있는 특징은 다음과 같다.

• 가중치 없는 방향 그래프가 주어진다.
• 입력 값으로 인접행렬이 주어진다.

i에서 j로 가는 길이가 양수라면, i에서 k를 거쳐 j를 간다는 말과도 같다. 이 말은 즉, 모든 정점에 대한 경로를 계산하겠다는 의미와도 같다.

그리고 그래프를 그려서 그대로 출력만 해주면 된다.

 

for k in range(n):
    for i in range(n):
        for j in range(n):
            if (graph[i][k] == 1 and graph[k][j] ==1) or graph[i][j]==1:
                graph[i][j]=1

이 코드는 플로이드 워셜 알고리즘을 문제 조건에 따라 변형한 코드이다.

쉽게 말하자면 i가 출발 노드, j가 도착 노드, k가 거쳐가는 노드이다.

그래서 i에서 j까지 가는 방법이 있다(=값이 1이다)면 graph[i][j]에 1이라고 체크를 해주는 것이다.

1→3→2 가 있다면 1→2 를 체크하고
1→2→1 이라면 1→1를 체크할 수 있다.

 

플로이드 워셜 알고리즘(Floyd Warshall)

플로이드 워셜 알고리즘에 대한 설명은 여기서 확인할 수 있다.

 

for i in range(n):
    print(*graph[i])

그리고 위와 같이 포인터(*)를 사용한다면 값이 아닌 주소에 접근한다. 그래서 이중 for문을 돌릴 필요 없이 값만 출력하는 것이 가능하다.