Baekjoon 백준 알고리즘 - 경로찾기 ( 11403 )

1.문제소개

• 모든 정점들간의 최단경로를 구하는 플로이드 와샬을 사용하면서, 출력 요구사항만 맞추면 된다.
• 시간복잡도는 for 루프가 3중으로 수행되기 때문에 O(n3) 이다.
• 공간복잡도는 행렬의 크기만큼 O(n2)이다.

2.코드

def floydWarshall(dag, N):
    for i in range(0, N):
        for j in range(0, N):
            if dag[i][j] == 0 and i != j:
                dag[i][j] = -1  # INF

    for k in range(0, N):
        for i in range(0, N):
            for j in range(0, N):
                if dag[i][k] > 0 and dag[k][j] > 0:
                    dag[i][j] = 1

    for i in range(0, N):
        for j in range(0, N):
            if dag[i][j] <= 0:
                print('{} '.format(0), end='')
            else:
                print('{} '.format(dag[i][j]), end='')
        print()


def main():
    N = int(input())
    dag = []
    for i in range(0, N):
        line = input().split(' ')
        dag += [[int(x) for x in line]]

    floydWarshall(dag, N)


if __name__ == '__main__':
    main()

3.코멘트

• 그래프 문제는 알고리즘도 어렵지만 언제나 전처리부분 작성이 성가시다..