[알고리즘] BOJ 21940 가운데에서 만나기 #Python

김상현·2022년 11월 24일

알고리즘

목록 보기

235/301

[BOJ] 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$ 가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.

📍 풀이

💡 고찰

그래프에 가중치가 있고, 모든 노드에서 모든 노드로의 최소 비용을 구해야 하는 경우는 플로이드 워셜(Floyd Warshall) 알고리즘을 적용해야 한다.
어려움을 겪은 부분은 주어진 조건에서 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다. 부분에서 최대가 최소가 되는 도시 를 이해하는 것이었다.
처음에는 준형이와 친구들이 살고 있는 도시(C)에서 X도시로 이동하는 모든 왕복비용의 합이 최소가 되는 도시를 구하는 줄 알았는데 예제 2 에서 정답이 일치하지 않아서 많은 고민을 하였다.
예제 2 의 결과를 기준으로 준형이와 친구들이 살고 있는 도시(C)에서 X도시로 이동하는 왕복비용 중 가장 큰 값을 하나만 추출하여 관리한 후에 마지막에 가장 큰 값 중 가장 작은 값을 기준으로 결과를 출력해야 한다는 것을 깨달았다.
문제를 풀 수 있는 능력도 중요하지만 문제를 이해하는 능력도 중요하다는 것을 배웠다.

📌 문제 풀이

✏️ [0] 간선 초기화

graph = [[maxsize] * (N+1) for _ in range(N+1)]
for A, B, T in edges:
    graph[A][B] = T
for i in range(1,N+1):
    graph[i][i] = 0

각 도시의 연결 상태(graph)를 maxsize 로 초기화한 상태에서 주어진 간선 정보(edges)를 통해 각 도시의 연결 상태를 초기화 한다.
A 도시에서 A 도시로 이동하는 즉, 자기 자신으로 이동하는 비용은 0 으로 초기화한다.

✏️ [1] 플로이드 워셜

for k in range(1,N+1):
    for j in range(1,N+1):
        for i in range(1,N+1):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j] # 최단 거리 갱신

초기화한 각 도시의 연결 상태(graph)를 플로이드 워셜 알고리즘을 적용하여 각 노드로 이동하는는데 사용되는 최소 비용을 계산한다.

✏️ [2] 최대 왕복시간 계산

cities = [0] * (N+1)
for X in range(1, N+1):
    maxValue = 0
    for c in C:
        if c == X or graph[c][X] == maxsize or graph[X][c] == maxsize: continue
        maxValue = max(maxValue, graph[X][c] + graph[c][X])
    cities[X] = maxValue

준형이와 친구들이 살고 있는 도시(C)에서 각 도시로 이동하는데 걸리는 최대 왕복 시간을 계산한다.

✏️ [3] 최소 왕복시간 계산

target = min(cities[1:])
for X in range(1,N+1):
    if cities[X] == target:
        answer.append(X)

위에서 구한 최대 왕복시간 중에서 가장 작은 왕복시간을 가진 모든 도시를 answer 에 저장한다.

✍ 코드

from sys import stdin, maxsize

def solution(N,edges,K,C):
    answer = []

    # [0] 간선 초기화
    graph = [[maxsize] * (N+1) for _ in range(N+1)]
    for A, B, T in edges:
        graph[A][B] = T
    for i in range(1,N+1):
        graph[i][i] = 0

    # [1] 플로이드워셜 알고리즘
    for k in range(1,N+1):
        for j in range(1,N+1):
            for i in range(1,N+1):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j] # 최단 거리 갱신
    
    # [2] 최대 왕복시간 계산
    cities = [0] * (N+1)
    for X in range(1, N+1):
        maxValue = 0
        for c in C:
            if c == X or graph[c][X] == maxsize or graph[X][c] == maxsize: continue
            maxValue = max(maxValue, graph[X][c] + graph[c][X])
        cities[X] = maxValue
    
    # [3] 최소 왕복시간 계산
    target = min(cities[1:])
    for X in range(1,N+1):
        if cities[X] == target:
            answer.append(X)
    
    return answer

# input
N, M = map(int,stdin.readline().split())
edges = list(tuple(map(int,stdin.readline().split())) for _ in range(M))
K = int(stdin.readline())
C = list(map(int,stdin.readline().split()))

# result
result = solution(N,edges,K,C)
print(*result)