[PS] BOJ 11403 경로 찾기

문제링크

플로이드워셜 기본원리를 사용하되, 최단거리를 찾는 것이 아니라 경로가 있는지만 확인하면 되는 비교적 간단한 문제

플로이드워셜 알고리즘은 전에 정리해둔 이것이 코딩테스트다 - 최단경로를 참고했다.

[제출한 코드]

n = int(input()) # 정점의 개수

graph = [[0] * (n) for _ in range(n)] # 그래프 초기화


# 그래프 인접행렬 입력받아 간선 존재 여부 갱신
for i in range(n):
    ith_list = list(map(int, input().split()))
    for j in range(n):
        if ith_list[j] == 1: # i에서 j로 가는 간선 존재하는지 확인
            graph[i][j] = 1
        
# i에서 j로 바로 연결된 간선 or 다른 정점을 거쳐서 갈 수 있는 경로 존재하면
# graph[i][j] = 1로 갱신
for k in range(n): # 경유 정점
    for i in range(n):
        for j in range(n):
            if (graph[i][j] == 1) or ((graph[i][k] and graph[k][j]) == 1):
                graph[i][j] = 1


# 그래프 출력
for a in range(n):
    for b in range(n):
        print(graph[a][b], end=" ")
    print()

if문 비교

코드를 제출하고 i에서 j로 가는 경로가 있는지 확인하는 3중 반복문에 있는 if문에서 graph[i][j] == 1을 빼도 되지 않을까하는 생각이 들었다.

왜냐하면 이미 앞선 반복문에서 i에서 j로로 바로 연결된 간선을 확인했기 때문에 현재 반복문에서는 or 뒷부분 (graph[i][k] and graph[k][j] == 1)만 확인해도 될 것 같았기 때문이다.

하지만 백준에 제출해본 결과 메모리는 동일하지만 40ms 정도 시간이 더 걸리게 되었다.

생각해보니 graph[i][j] == 1을 만족하면 or 뒷부분을 확인하지 않아도 되는데, 이를 빼면 매번 graph[i][k]와 graph[k][j] 두 개를 확인해야 하기 때문에 시간이 더 걸리는 현상이 생긴 것 같다.