알고리즘 스터디 - 백준 2644번 : 촌수계산

문제 해석

• 전체 사람의 수 n 명을 입력받음
• 촌수를 계산해야하는 두 사람의 번호
• 부모 자식들 간의 관계의 개수 m
• m개의 부모 자식간의 두 번호 x(부모), y(자식)이 나옴

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력 만약 친척 관계가 없으면 -1임

어떤 알고리즘을 사용해야할까?

• 일단, 기본적으로 길이가 1인 그래프 노드간 거리를 나타내는 알고리즘을 사용하면 될 것같다.
• 그래프 노드를 탐색을 하면서 길이를 계산하는 것에는 다익스트라, BFS, DFS가 있는데 여기서 BFS 부터 해보도록 하겠다.

알고리즘 코드

n = int(input())

cal_x, cal_y = map(int, input().split())

m = int(input())

graph = [[] for _ in range(n+1)]

for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def bfs(graph, start, end):
    q = []
    visited = []
    count = 0
    q.append(start)

    while q:
        count += 1

        for _ in range(len(q)): 
            position = q.pop(0)
            if position == end:
                return count - 1
            for node in graph[position]:
                if node not in visited:
                    visited.append(node)
                    q.append(node) 

    return -1

print(bfs(graph, cal_x, cal_y))