[백준 2644] 촌수계산 - Python

백준 2644번 촌수계산 !

입력받은 값에서 사용해야할 node가 정해져있기 때문에 bfs 함수를 사용할때 바로 값을 파라미터로 넣어주면 된다 !

 

bfs문제 중 쉬운 문제였지만, count하는데에 쪼금 시간을 날렸다 ...

 

처음에 아무 생각없이 변수 cnt로 방문시 증가만 해줬는데다음 거리를 현재 거리의 +1해주어서 잘 마무리했다 !!

from collections import deque
#전체 사람 수
n = int(input())

#촌수를 계싼해야 하는 서로 다른 두 사람의 번호
person1, person2 = map(int,input().split())

#부모 자식들 간의 관계의 개수
m = int(input())

result = [0] * (n+1)
def bfs(startNode,endNode):
    #print(visited)
    queue = deque()
    queue.append(startNode)
    cnt = 0
    #print(queue)
    while queue:
        start = queue.popleft()
        if start == endNode:
            return result[endNode]
        else:
            for i in graph[start]:
                if visited[i]==False:
                    visited[i] = True
                    result[i] = result[start]+1
                    queue.append(i)
    return -1

graph= [[] for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
    #x는 y의 부모
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

print(bfs(person1,person2))