알고리즘/그래프
백준 2644 촌수계산 (Python)
한뜽규
2024. 2. 12. 22:04
728x90
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
해당 문제의 분류는 분명 그래프에 너비 우선 탐색이겠지만, 딱 보자마자 플로이드 와샬이 생각이 나서 해당 방법으로 해결했다.
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)