BOJ 17270 - 연예인은 힘들어 링크
(2022.11.07 기준 G2)
(치팅안하기는 힘들어..?)

문제

문제에 제시되어 있는 네 조건에 맞춰 지헌이와 성하와의 약속 장소 출력

알고리즘

약속 장소가 가능한 모든 장소로의 최단 거리의 합과 여러 요소를 비교해야 한다.
V가 100 이하이므로 플로이드 워셜이 가능하다.

풀이

V가 100 이하이며 모든 위치 간 거리를 알아야 하므로 플로이드 워셜을 돌려주자.
그리고 조건 4개를 맞춰보자.

먼저 조건 1은 지헌과 성하의 출발지를 제외해야 한다.
그리고 조건 2는 성하와 지헌의 최단 거리의 합이 최소인 약속 장소를 모두 찾아야 한다.
최단 거리의 합을 무한대로 저장해두고, 거리의 합이 최소로 갱신될 때마다 리스트를 초기화해준다. 물론, 현재 최단 거리의 합과 특정 약속 장소로의 거리의 합이 같으면 리스트에 그 약속 장소를 넣어주면 된다.

# 조건 1~2 고려
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:
        	cand.append(i)

그런데 여기서 조건 3을 잘 봐야 한다.
성하가 지헌보다 먼저 도착하면 안된다.
그러므로 matrix[J][i] <= matrix[S][i] 를 추가해주자.

# 조건 1~3 고려
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)

여기서 또 조건 4를 보자.
약속 장소 후보가 여러 개이면 그 중 지헌의 최단 거리가 최소가 되는 약속 장소. 그것도 여러 개이면 번호가 가장 작은 장소가 최종 약속 장소가 된다.

그러므로 cand에 추가할 때, matrix[J][i]를 같이 추가해 이를 기준으로 오름차순으로 정렬하여 맨 앞에 오는 약속 장소가 최종 약속 장소라고 생각하면 된다.

# 조건 1~4 고려
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]])
answer = sorted(cand, key = lambda x: x[1])[0][0] + 1 # 조건 4

주의사항

조건을 무조건 차례대로 고려해야 한다.
하기 쉬운 실수가 조건 3을 고려하면서 조건 2를 고려할 수 있는데, 그러면 틀린다.

코드

import sys; input = sys.stdin.readline
from math import inf

def solve():
    V, M = map(int, input().split())
    matrix = [[inf] * V for _ in range(V)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1; b -= 1 # 0-based Index
        if c < matrix[a][b]:
            matrix[a][b] = c
            matrix[b][a] = 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)

solve()

여담

조건을 순서대로 고려하지 않아 맞왜틀한 문제.
이런 식으로 틀리게 하는 문제는 좀 싫다..