[백준] 11403 - 경로 찾기

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

11403번: 경로 찾기

문제 한줄 이해

-가중치가 없는 방향 그래프가 있을 때 각 노드 입장에서 다른 노드를 거쳐서라도 갈 수 있는지 판단하기

생각난 풀이

1번째 방법: 각 노드들이 중간 다리 역할을 해주면서 탐색을 하는 방법이 생각났다.

예제를 그림으로 그리면 위와 같다. 이때 0번 노드 입장에서 1번 노드가 중간다리를 해주면 2번 노드로 갈 수 있다. 

따라서 graph[i][k] + graph[k][j]가 2라면 graph[i][j]는 1로 바꿔줄수 있다.

import sys
n = int(sys.stdin.readline())
graph = []

for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

# 각 지점이 경유지가 됐을때 기준으로 탐색을 하면된다.
for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][k] + graph[k][j] ==2 :
                graph[i][j] = 1

for i in graph:
    print(*i)