BOJ 18243 - Small World Network

문제

백준 온라인 저지 - 18243번

풀이 과정

입력으로 주어진 친구 관계를 기반으로 작은 세상 네트워크 를 만족하는지 판단하는 문제입니다.

서로 다른 두 친구사이에 도달하기 위한 거리를 모두 계산해서 6단계 이하인지 확인하면 됩니다.

이를 위해 플로이드 와샬 알고리즘을 사용해서 모든 정점간의 거리 값을 O(N^3) 의 시간 복잡도로 계산하면 됩니다.

코드

import sys

N, K = list(map(int, sys.stdin.readline().split()))
edges = [list(map(int, sys.stdin.readline().split())) for _ in range(K)]


def make_graph():
    graph = [[sys.maxsize] * N for _ in range(N)]

    for frm, to in edges:
        graph[frm - 1][to - 1] = 1
        graph[to - 1][frm - 1] = 1

    return graph


def floyd(graph):
    for v in range(N):
        graph[v][v] = 0

    for k in range(N):
        for u in range(N):
            for v in range(N):
                graph[u][v] = min(graph[u][v], graph[u][k] + graph[k][v])


def solution():
    graph = make_graph()
    floyd(graph)

    for frm in range(N):
        for to in range(N):
            if graph[frm][to] > 6:
                return 'Big World!'

    return 'Small World!'


print(solution())