[백준] 경로 찾기 (11403번)

문제 링크:

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

회고:

• 모든 정점에서 모든 정점까지의 가능한 경로를 찾아야 하는 문제이므로, 플로이드 와샬 알고리즘을 사용했다.
• 다만, 경로 유무만 파악하면 되기 때문에 최단 거리까지는 구하지 않았다.

python

import sys


def solution(graph):
    N = len(graph)

    is_exist = "1"

    # k: 거쳐가는 노드
    for k in range(N):
        # i: 출발 노드
        for i in range(N):
            #  j: 도착 노드
            for j in range(N):
                # k를 거쳐가는 노드가 있는지 구한다.
                if graph[i][k] == is_exist and graph[k][j] == is_exist:
                    graph[i][j] = is_exist

    return graph


if __name__ == "__main__":
    # 정점의 개수
    N = int(input())

    # 노드 간 연결 정보
    graph = []
    for i in range(N):
        graph.append(sys.stdin.readline().split())

    result = solution(graph)
    for row in result:
        sys.stdout.write(" ".join(row) + "\n")

# input

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

# output

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0