[백준 2644] 촌수계산(python)

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

2644번: 촌수계산

촌수계산 문제

부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 문제

 

#사용 알고리즘

너비 우선 탐색(BFS)

 

📌문제 접근 포인트

1. 촌수 계산을 하는 문제. 즉, 촌수는 한칸 넘어갈 때마다 해당 위치에서 촌수가 +1씩 증가한다.

2. 1씩 증가하는 탐색 방법 중 가장 보편적인 방법인 BFS를 구현하면 된다. 일반 기본 BFS 구현 문제들과 풀이 방식이 동일하다.

⚙ 내가 푼 정답 코드

def find(a):
    visited = [0]*(n+1)
    visited[a] = 1
    queue = deque([a])
    while queue:
        p = queue.popleft()
        for i in graph[p]:
            if not visited[i]:
                visited[i] = visited[p] + 1
                queue.append(i)

    return visited[c]-1 #찾을 촌수 -1 반환 시 요구 조건에 맞게 촌수 관게 없을 경우 -1 반환


import sys
from collections import deque
n = int(sys.stdin.readline())
r, c = map(int, sys.stdin.readline().split()) # 시작 촌수, 찾을 촌수
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

print(find(r))