문제

https://www.acmicpc.net/problem/18243

풀이

케빈 베이컨의 6단계 법칙과 관련된 문제이다.

모든 정점들이 최소 6단계 이하로 연결되어 있는지 확인해야한다.
다음과 같은 조건들로 플로이드 와샬 알고리즘을 사용해야겠다고 생각했다.

• 1 <= N <= 100
  (O(N^3)으로 충분히 해결 가능)
• 모든 정점들간의 최단거리 필요
  (물론 다익스트라 or BFS를 각 정점마다 돌려도 가능하다.)

플로이드 와샬 알고리즘을 통해 모든 정점들의 최단거리를 구하고 만약 그 거리가 7이상인지 판단하면 된다.

CODE

import sys

input = sys.stdin.readline
inf = sys.maxsize


def print_world(n, f):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if f[i][j] > 6:
                return "Big World!"

    return "Small World!"


def floyd(n, f):
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                f[i][j] = min(f[i][j], f[i][k] + f[k][j])

    return print_world(n, f)


def get_f(n, k):
    f = [[0 if i == j else inf for j in range(n + 1)] for i in range(n + 1)]

    for i in range(k):
        u, v = map(int, input().split())
        f[u][v] = f[v][u] = 1

    return f


def solve():
    n, k = map(int, input().split())
    return floyd(n, get_f(n, k))


print(solve())