[백준/Python]1959: 운동

문제

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

백준 문제집 - 0x1C강 - 플로이드 알고리즘

알고리즘: 그래프 이론, 최단 경로, 플로이드-워셜

---

풀이

 

두 마을을 왕복하는 경우도 사이클에 포함된다.
즉, 플로이드 워셜로 각 마을 사이의 최단거리값을 구한 다음 한 마을을 기점으로 다른 마을까지의 왕복거리를 계산하면 된다.
시작마을 A, 도착마을 B일때 A → B의 값 + B → A의 값이 가장 작은 경우를 선택하면 되는 것이다. (일방통행이므로 A-B, B-A의 값이 다르다.)

 

사실 문제 자체는 어렵지 않다. 단순한 플로이드 워셜 문제에 가깝다.
하지만 조건식을 어떻게 작성하는지에 따라 시간초과가 날 수도 있으니 주의해야한다.

 

전체적인 과정은 아래와 같다.

1. 각 마을 사이의 거리를 그래프에 저장. (a, b)쌍이 같은 도로가 여러번 주어지지 않음.
2. 플로이드 워셜 수행
3. 시작 마을 A를 기준으로 다른 마을 B까지의 왕복 거리들을 계산.
   • 가장 짧은 거리가 결과값.

 

전체 코드

# 메모리: 37660KB / 시간: 5832ms
from sys import stdin


input = stdin.readline
INF = float("inf")

def main():
    V, E = map(int, input().split())
    graph = [[INF] * V for _ in range(V)]

    for _ in range(E):
        a, b, c = map(int, input().split())
        graph[a-1][b-1] = c

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

    min_dis = INF

    for i in range(V):
        for j in range(i+1, V):
            if min_dis > graph[i][j] + graph[j][i]:
                min_dis = graph[i][j] + graph[j][i]

    print(min_dis if min_dis != INF else -1)


main()

 

참고로 아래 코드는 시간초과다.

from sys import stdin


input = stdin.readline
INF = float("inf")

def main():
    V, E = map(int, input().split())
    graph = [[INF] * (V+1) for _ in range(V+1)]

    for _ in range(E):
        a, b, c = map(int, input().split())
        graph[a][b] = c

    for k in range(1, V+1):
        for i in range(1, V+1):
            for j in range(1, V+1):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    min_dis = INF

    for i in range(1, V+1):
        for j in range(1, V+1):
            min_dis = min(min_dis, graph[i][j] + graph[j][i])

    print(min_dis if min_dis != INF else -1)


main()

 

⭐주요 차이점은 아래와 같다.

1. min() 대신 <, > 비교연산자 사용
   • 둘 다 덧셈연산 후 비교하는건 똑같음.
   • 하지만 min()의 경우 참/거짓과 상관없이 무조건 "대입"을 하게 됨.
2. 리스트 크기 설정
   • 마을 번호는 1부터 시작되므로 그래프 저장 시 -1처리를 해주거나 리스트 크기를 (V+1)로 설정해야함. (다만 이 문제에서의 결정적 포인트는 아니다.)
3. 마지막 for문의 범위 설정
   • 🚨이게 제일 중요하다고 생각한다.
   • 문제에서 원하는 값은 "거리"값이지 "어떤 마을"인지가 중요한게 아니다.
   • (AB, BA)값은 시작마을을 B로 설정했을때의 값(BA, AB)와도 같으므로, 순열이 아닌 조합으로 판단해도 된다.

사실 1번이 주요 포인트라고 생각했는데, 뭔가 이상해서 다시 돌려보니 3번이었다.
중요도 순위는 3 > 1 >> 2 인듯 싶다...
리스트 크기만 V로 변경했을때는 똑같이 시간초과였고, for문 범위 변경 or 비교연산자 사용 중 하나만 적용해도 통과된다.