백준 17270 연예인은 힘들어 파이썬

🔗 백준 17270 연예인은 힘들어 

 

📌오늘의 학습 키워드

• 플로이드 - 워셜
• 조건을 잘 읽자

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

플로이드 - 워셜

• 모든 정점에서 다른 모든 정점으로 가는 최소 거리를 찾는 방법이다.
• 모든 정점 사이의 최소거리를 2차원 배열에 저장할 것이다.

1. 2차원 배열을 INF로 초기화 한다.
2. [ i ][ i ] 인 경우 자기 자신 이므로 0으로 설정한다. (이 문제에서는 따로 예외 처리해서 그냥 INF로 놔뒀다)
3. 각 정점을 반복문을 돌면서 이 정점를 거쳐서 출발 정점에서 목표 정점으로 향할 때의 거리가 기존 저장되어 있는 배열보다 짧으면 최소거리를 업데이트 해준다.

📚오늘의 회고

이 문제는 조건을 하나하나 순서대로 구현하는 것이 중요했다.

• 1. 지헌이와 성하의 위치는 약속장소가 되면 안된다.
  2. 지헌이가 걸리는 시간 + 성하가 걸리는 시간이 최소여야 한다.
  3. 지헌이가 걸리는 시간 < 성하가 걸리는 시간 이여야 한다.
  4. 해당 사항을 모두 만족하는 약속장소가 여러곳이라면
     • 지헌이가 걸리는 시간이 최소 인 곳이 약속 장소가 된다.
       • 이 장소도 여러 곳이라면 번호가 가장 작은 곳이 약속장소이다.

틀린 이유들 😅

1. 지헌이가 걸리는 시간 + 성하가 걸리는 시간이 최소이면서 지헌이가 걸리는 시간이 더 적어야 하는데, 지헌이가 걸리는 시간이 적은 것들 중에서 지헌이가 걸리는 시간 + 성하가 걸리는 시간이 최소인 것을 골라서 틀렸었다.
2. 지헌이와 성하의 위치는 약속장소이면 안되는데 만약 간선이 1 1 3 이런 식으로 들어오는 경우를 처리해주지 않아서 틀렸었다. 정확하게 인덱스 번호가 같은 경우 배열을 업데이트 하지 않도록 고쳤다.

[🤓문제 해결 코드]

import sys

V, M = map(int, input().split())
dists = [list(map(int, input().split())) for _ in range(M)]
J, S = map(int, input().split())

min_dist = [[sys.maxsize for _ in range(V + 1)] for _ in range(V + 1)]

# 최초 거리 저장
for dist in dists:
    a, b, c = dist
    if a == b:
        continue
    if min_dist[a][b] > c:
        min_dist[a][b] = c
        min_dist[b][a] = c

# 특정 정점을 지났을 때 최소 거리 업데이트
for i in range(1, V + 1):
    for j in range(1, V + 1):
        for k in range(j + 1, V + 1):
            if min_dist[j][i] + min_dist[k][i] < min_dist[j][k]:
                min_dist[j][k] = min_dist[j][i] + min_dist[k][i]
                min_dist[k][j] = min_dist[j][i] + min_dist[k][i]


dist_J = min_dist[J]
dist_S = min_dist[S]

# J - S 는 약속 장소가 될 수 없으므로
dist_J[S] = sys.maxsize
dist_S[J] = sys.maxsize

sum_dist = []

for i in range(len(dist_J)):
    sum_dist.append(dist_J[i] + dist_S[i])

if min(sum_dist) >= sys.maxsize:
    print(-1)
else:
    min_idx = -1
    min_j_dist = sys.maxsize
    for i in range(1, len(sum_dist)):
        if sum_dist[i] == min(sum_dist) and dist_J[i] <= dist_S[i]:
            if min_j_dist > dist_J[i]:
                min_j_dist = dist_J[i]
                min_idx = i
    print(min_idx)

[반례]

2 3
1 1 3
2 2 3
1 2 2
1 2

답: -1

5 6
1 2 2
1 3 2
1 4 3
2 5 3
3 5 3
4 5 1
1 5

답: -1