백준[21278] 호석이 두 마리 치킨 (Python3, bfs)

분석하고 보니 플로이드 문제였지만, 시간 복잡도를 계산해 보니 시간이 충분해서 bfs로 풀었다.

bfs로 풀 수 있다 생각한 이유

치킨집의 쌍을 구하면 (1, 100), (2, 100) ... (99, 100)로 약 5,000개의 쌍이 생긴다.

간선이 생길 수 있는 개수도 최대가 약 5000개다.

치킨집으로 정한 두 인덱스를 기준으로 bfs 탐색을 진행하면 최악의 경우에 각각 전체를 탐색해야 하고 이러면 10,000번의 탐색이 진행된다.

 

각 쌍이 10,000번의 탐색을 수행한다 하면
5,000 * 10,000 = 50,000,000 번의 탐색 즉, 약 0.5초 만에 결과를 낼 수 있단 것을 발견해, bfs로 풀이했다.

 

코드

from collections import deque

N, M = map(int, input().split())
nodes = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v = map(int, input().split())
    nodes[u].append(v)
    nodes[v].append(u)
chicken = [0] * 2


def main():
    answerI, answerJ = 0, 0
    minCost = float("inf")
    for i in range(1, N + 1):
        chicken[0] = i
        for j in range(i + 1, N + 1):
            chicken[1] = j
            ret = bfs()
            if minCost > ret:
                minCost = ret
                answerI, answerJ = i, j

    print(answerI, answerJ, minCost)


def bfs():
    q = deque()
    q.append((chicken[0], 1))
    q.append((chicken[1], 1))
    cost = [float("inf")] * (N + 1)
    cost[chicken[0]] = 0
    cost[chicken[1]] = 0
    while q:
        here, hereC = q.popleft()
        for there in nodes[here]:
            if cost[there] > cost[here] + 1:
                cost[there] = cost[here] + 1
                q.append((there, hereC + 1))
    total = 0
    for i in range(1, N + 1):
        if cost[i] != float("inf"):
            total += cost[i]
    return total * 2




if __name__ == '__main__':
    main()