100년 뒤 개발자 한승규입니다.

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

해당 문제의 분류는 분명 그래프에 너비 우선 탐색이겠지만, 딱 보자마자 플로이드 와샬이 생각이 나서 해당 방법으로 해결했다.

n * n 크기의 배열을 만들고 3중 반복문으로 각 촌수를 계산할 수 있도록 하였다.

import sys

n = int(sys.stdin.readline().strip())

target_a, target_b = map(int, sys.stdin.readline().split())

family = [[float('inf') for _ in range(n)] for _ in range(n)]

for _ in range(int(sys.stdin.readline().strip())):
    a, b = map(int, sys.stdin.readline().split())
    family[a-1][b-1] = 1
    family[b-1][a-1] = 1

for i in range(n):
    for t in range(n):
        for k in range(n):
            if t != k:
                family[t][k] = min(family[t][k], family[t][i] + family[i][k])


print(family[target_a - 1][target_b - 1] if family[target_a - 1][target_b - 1] != float('inf') else -1)