백준 21278 - 호석이 두 마리 치킨

문제 설명

컴공의 미래...?

입출력 및 제한사항

풀이

 

문제 요약은 다음과 같다. 건물은 1부터 N, 도로는 무가중치 양방향(이동 시간 = 1), 치킨집 두 곳을 정해 모든 건물에서 더 가까운 치킨집까지 이동하는 시간의 합(왕복)이 최소가 되게 하는 문제이다. 만약 합이 같은 후보가 여러 개면 건물 번호가 더 작은 쌍(A가 작을수록, 같다면 B가 작을수록)을 택한다.

 

모든 건물에 대해서 최단거리를 알아야하기 때문에 플로이드-워셜로 최단거리를 구하고 모든 쌍에 대한 최단거리의 왕복을 계산해주었다. 크게 알고리즘적으로 필요하다기보단 구현만 주의해서 해주면 될 것 같다! 코드를 확인해보자.

 

내 코드

import sys
input = sys.stdin.readline
mis = lambda: map(int, input().split())
INF = float('inf')

n, m = mis()
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a, b = mis()
    
    graph[a][b] = 1
    graph[b][a] = 1

for k in range(1, n+1):
    graph[k][k] = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ans = (INF, 1, 2)
for i in range(1, n+1):
    for j in range(i+1, n+1):
        s = 0
        for k in range(1, n+1):
            s += min(graph[k][i], graph[k][j])
        s *= 2

        cand = (s, i, j)
        ans = min(ans, cand)

print(ans[1], ans[2], ans[0])

플로이드-워셜로 모든 최단거리를 구한 뒤 모든 순서쌍에 대해서 최단거리를 구한다. 단순히 반복문으로 구현하였으며, Combination을 이용할 수도 있을 것 같다.

 

시간 복잡도

플로이드-워셜: O(n^3)

최단거리 탐색: O(n^3)

고찰

최단거리를 찾는 대표적인 알고리즘인 다익스트라나 BFS로도 풀이가 가능하다. 시간이 없어서 다른 풀이는 해보지 못했으니,,, 간단하게 시간복잡도만 생각해보자면 모든 최단거리를 찾는 시간은 줄어들겠지만 결국 모든 쌍에 대해 최단거리를 구하는데에 O(n^3)이 들기 때문에 지배항이 바뀌지 않아 조금 최적화되는 수준일 것이라고 생각한다.