백준 18243 Small World Network(플로이드-와샬, BFS)

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

18243번: Small World Network

 

<플로이드-와샬>

import sys

n, k = list(map(int,input().split()))

edges = [list(map(int,input().split())) for _ in range(k)]
INF = sys.maxsize

def make_graph():
    graph = [[INF] * 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())

<BFS>

 

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
graph = [[] * (N+1) for i in range(N+1)]
check = 0
for _ in range(K):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)
def bfs(x):
    q = deque()
    q.append(x)
    visited[x] = 0

    while q:
        x = q.popleft()
        for nx in graph[x]:
            if visited[nx] == -1:
                q.append(nx)
                visited[nx] = visited[x] + 1
    return

for i in range(1, N+1):
    visited = [-1] * (N + 1)
    bfs(i)
    if max(visited) > 6 or -1 in visited[1:]:
        check = 1
        break

if not check:
    print('Small World!')
else:
    print('Big World!')