99클럽 코테 스터디 5기 5일차 TIL + 플로이드 워셜

-  오늘의 학습 키워드

Floyd-warshall(최단경로, 플로이드-워셜 알고리즘)

-  공부한 내용 본인의 언어로 정리하기

# https://www.acmicpc.net/problem/17270
import sys
input = sys.stdin.readline

INF = int(1e9)

v,m = map(int,input().split())
matrix = [[INF] * v for _ in range(v)]

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

for k in range(v) :
    matrix[k][k] = 0
    for i in range(v) :
        for j in range(v) :
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

J, S = map(int, input().split())
J -= 1; S -= 1 # 0-based Index
SUM = INF # 최단 거리의 합. 초기엔 무한대
cand = [] # 약속 장소 후보 리스트
for i in range(v):
    if i not in [J, S]: # 조건 1
        s = matrix[J][i] + matrix[S][i]
        # 조건 2
        if s < SUM: # 거리의 합이 갱신 되면 리스트 초기화
            SUM = s
            cand = []
        if s == SUM and matrix[J][i] <= matrix[S][i]: # 조건 3
            cand.append([i, matrix[J][i]])

# 조건 4를 고려하여 정렬 후 맨 앞에 오는 약속 장소 출력
print(sorted(cand, key = lambda x: x[1])[0][0] + 1) if cand else print(-1)

- 오늘의 회고

1. 어떤 문제가 있었고, 나는 어떤 시도를 했는지

나는 처음에는 다익스트라로 풀어보려고 했다. 다익스트라를 통해서 지헌이와 성하 사이의 최단 거리를 구한 다음 조건에 맞는 경로를 찾으려고 했다.

2. 어떻게 해결했는지

문제를 풀었는데 자꾸 채점을 하면 틀렸다. 다음 조건을 하나하나 다 체크해서 신경써줘야 해서 까다로웠던거 같다

1. 지헌이의 출발 위치와 성하의 출발 위치는 새로운 약속 장소가 될 수 없다.
2. 성품도 훌륭한 지헌이는 새로운 약속 장소는 지헌이가 걸리는 최단 시간과 성하가 걸리는 최단 시간의 합이 최소가 되도록 하고 싶다.
3. 지헌이가 더 늦게 도착하면 성하에게 안좋은 소리를 들을 것이 뻔하기에, 1번과 2번 조건을 만족하는 장소 중에서도 지헌이가 성하보다 늦게 도착하는 곳은 약속 장소가 될 수 없다.
4. 위의 세 조건을 모두 만족하는 약속 장소가 여러 곳이 있다면, 그 중에 지헌이로부터 가장 가까운 곳이 최종 약속 장소가 된다. 그런 장소도 여러 곳이 있다면, 그 중에 번호가 가장 작은 장소가 최종 약속 장소가 된다.

3. 무엇을 새롭게 알았는지

최단 경로 문제에서 다익스트라 말고 플로이드 워셜을 사용해야 하는 경우에 대해 알게 되었습니다