BOJ - 21278

백준 문제 링크
호석이 두 마리 치킨

❓접근법

1. 플로이드 워셜 알고리즘을 활용했다.
2. 플로이드 워셜 소스코드를 전개해 최단 거리 테이블을 갱신해준다.
3. 이제 건물의 조합을 만들어야 하는데, 코드는 다음과 같다.

for a in range(1, n + 1):
    for b in range(1, n + 1): # 건물 2개를 뽑음
        t = 0
        for k in range(1, n + 1):
            t += min(graph[k][a] * 2 , graph[k][b] * 2) # k -> a, k -> b 중 짧은 것
        if answer > t:
            answer = t
            result = [a, b, t] # 건물 2개와 모든 도시에서의 왕복 시간의 합

4. 마지막으로 result를 출력하면 끝!

👌🏻코드

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

INF = int(1e9)

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0
            
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
    
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b] , graph[a][k] + graph[k][b])

answer = INF
result = []

for a in range(1, n + 1):
    for b in range(1, n + 1): # 건물 2개를 뽑음
        t = 0
        for k in range(1, n + 1):
            t += min(graph[k][a] * 2 , graph[k][b] * 2) # k -> a, k -> b 중 짧은 것
        
        if answer > t:
            answer = t
            result = [a, b, t] # 건물 2개와 모든 도시에서의 왕복 시간의 합
            
print(*result)