2664번 촌수계산

문제 설명

2644번: 촌수계산

 

나의 풀이

from collections import deque, defaultdict


def relation_people(people, start_person, relation_graph):
    q = deque()
    q.append(start_person)
    chon_list = [-1] * (people + 1)
    chon_list[start_person] = 0

    while q:
        cur_person = q.popleft()

        for person in relation_graph[cur_person]:
            if chon_list[person] == -1:
                chon_list[person] = chon_list[cur_person] + 1
                q.append(person)
    
    return chon_list

people = int(input())
start_person, target_person = map(int, input().split())
relations = int(input())
relation_graph = defaultdict(list)
for _ in range(relations):
    parent, child = map(int, input().split())
    relation_graph[parent].append(child)
    relation_graph[child].append(parent) 

answer = relation_people(people, start_person, relation_graph)
print(answer[target_person])

촌수 정보가 담긴 리스트를 만들고 각 인덱스가 시작하는 사람과의 촌수 정보가 담긴다. bfs함수를 시작 노드로 부터 인접 노드들을 돌떄마다 +1을 해주어 촌수 정보리스트를 업데이트! 

 

*각 노드들의 관계를 그래프로 그려보고 문제를 풀어보자!