코드

n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))
    
def floyid(n):
    
    # k => 거쳐가는 경로
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # i => k => j의 경로가 존재
                # 1 and 1 => 1이 경로가 존재한다는 의미
                if graph[i][k] and graph[k][j]:
                    
                    # 경로가 있다면 1로 바꿔줌
                    graph[i][j] = 1
                    
floyid(n)

for i in graph:
    for j in i:
        print(j, end = ' ')
    print()

문제 해설

경로 찾기(플로이드)

플로이드 워셜 알고리즘으로 쉽게 풀 수 있는 문제이다.

플로이드 워셜 참고

사실 나는 아직 많은 문제를 풀지 않아 플로이드 워셜을 사용해야 하는 지도 모르고 접근했다. 한참을 해매다가 결국 구글링을 참고하여 구현에 성공… ㅠㅠ 비교적 간단한 로직으로 구현이 가능해서 이해하는 것이 어렵진 않았지만 문제를 보고 어떤 알고리즘을 적용해야 할지 파악할 수 있는 능력을 열심히 길러야겠다.

댓글남기기

참고