[백준 11403번] 경로 찾기 python

 

- 문제 유형 : 그래프 탐색, 플로이드 와샬

- 소요 시간 : 약 2시간

※ 플로이드 와샬 : '모든 정점'에서 '모든 정점'으로의 최단 경로

(다익스트라 알고리즘 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘)

핵심은 '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것.

 

https://blog.naver.com/ndb796/221234427842 참고

 

- 어려웠던 점 : bfs, dfs 문제이겠거니 생각하다가 '거쳐가는 정점'이 있을 때가 존재한다는 이유로, 어떻게 구현할지 고민함.

 

[코드]

N = int(input())
graph = []
for i in range(N):
    li = list(map(int, input().split()))
    graph.append(li)    
# print(graph)

for p in range(N) :
    for q in range(N) :
        for r in range(N):
            if graph[q][p] + graph[p][r] == 2 :
                graph[q][r] = 1

for j in range(N):
    for k in range(N):
        print(graph[j][k], end = " ")
    print()

알고 보면 생각보다 간단한 구현인데

for p in range(N) :

    for q in range(N) :

        for r in range(N):

            if graph[q][p] + graph[p][r] == 2 :

                graph[q][r] = 1

이 부분을 캐치해내지 못해서 헤맸었다.

ex) graph[0][1] + graph[1][2] = 1 + 1 = 2

=>graph[0][2] = 1

graph[0][2] + graph[2][0] = 1 + 1 = 2

=>graph[0][0] = 1

 

이런식으로 체크할 수 있다.