[BOJ 21940🥇4] 가운데에서 만나기 (Python)

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

21940번: 가운데에서 만나기

문제

준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다.

도시를 연결하는 도로는 일방 통행만 있어서 도시 A_i에서 도시 B_i로 가는 시간과 도시 B_i에서 도시 A_i로 가는 시간이 다를 수 있다.

준형이와 친구들은 아래 조건을 만족하는 도시 X를 선택하여 거기서 만나려고 한다.

• 왕복시간은 자신이 살고 있는 도시에서 도시 X로 이동하는 시간과 도시 X에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다.
• 준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다.
• 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다.
• 준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다.

도시가 많다보니 계산하기 힘들다. 준형이와 친구들을 대신하여 도시 X를 알려주자.

입력

첫 번째 줄에는 도시의 개수 N과 도로의 개수 M이 주어진다.

두 번째 줄부터 M + 1줄까지 도시 A_i, 도시 B_i, 도시 A_i에서 도시 B_i로 이동하는데 걸리는 시간 T_i가 공백으로 구분되어 주어진다.

 M + 2줄에는 준형이와 친구들의 총 인원 K가 주어진다.

 M + 3줄에는 준형이와 친구들이 살고 있는 도시의 번호 C_i가 공백으로 구분되어 주어진다.

출력

위 조건을 만족하는 도시 X의 번호를 출력한다. 만약 가능한 도시 X가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.

제한

•  3≤ N ≤200
•  2≤ K ≤ N 
•  1≤ M ≤ N∗(N−1) 
•  1≤ C_i ≤ N
•  1≤ T ≤1,000 

예제 입력 1 

4 9
1 2 9
2 3 9
3 1 9
1 4 1
4 1 1
2 4 1
4 2 1
3 4 1
4 3 1
3
1 2 3

예제 출력 1 

4

예제 입력 2

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

예제 출력 2 

1 2 3

 

⭕ CODE

n,m = map(int,input().split())

inf = int(1e9)

arr = [[inf] * (n+1) for _ in range(n+1)]

# a에서 b까지 가는 시간 c
# a -> b와 b -> a 의 시간이 다를 수 있으므로 단방향 이다.
# 즉 arr[b][a] = c 는 작성 x
for _ in range(m):
    a,b,c = map(int,input().split())
    arr[a][b] = c

# 자기자신으로 가는 경우 0
for i in range(1,n+1):
    arr[i][i] = 0

# 플로이드 워셜 사용
for i in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            arr[a][b] = min(arr[a][b], arr[a][i] + arr[i][b])

# 친구들의 총 인원 k
k = int(input())

# 준형이와 친구들의 도시 리스트
city = list(map(int,input().split()))


result = []

# 모든 도시 x 조사
for x in range(1,n+1):
	# 최대치 max_reuslt 구하기
    max_result = 0
    # 친구들의 도시 리스트
    for i in city:
    	# 도시가 친구들 도시에 없고 서로 갈 수 있다면
        if i != x and arr[i][x] != inf and arr[x][i] != inf:
        	# max_result 구하기 왕복 최대값
            max_result = max(max_result, arr[i][x] + arr[x][i])
    # 모든 최대값 result에 넣어주기
    result.append(max_result)

# 최대값들 중 최소값 구하기
min_result = min(result)

# 최소가 되는 도시 구하기
for i in range(n):
    if result[i] == min_result:
        print(i+1, end=' ')

✏️ Comment

처음에는 플로이드 워셜까지 사용하고 이제 무엇을 해야하는지 잘 몰랐다. 문제를 잘 읽자

최대 중 최소를 구하는 것이였는데 처음에는 result안에 넣을 생각을 하지 않고 그냥 최소 result만 구했다. 그러면 어느 도시인지 판별이 불가능해 result안에 모든 최대값들을 넣고 그 중에 최소를 골라 result와 비교하여 도시들을 구하였다.