BOJ - 2644 - 촌수계산

Updated:

import sys
from collections import deque

def BFS(graph, source, target, N):
    count = 0
    visit = [False] * (N + 1)

    dq = deque()
    dq.append((source, 0))

    while dq:
        vertex, weight = dq.popleft()
        count = weight

        if vertex == target:
            return count

        if visit[vertex] is False:
            count += 1
            visit[vertex] = True
            for v in graph[vertex]:
                if visit[v] is False:
                    dq.append((v, count))
    return -1

def solution():
    N = int(input())
    X, Y = map(int, sys.stdin.readline().split())
    T = int(input())
    graph = [[] for _ in range(N+1)]

    for _ in range(T):
        x, y = map(int, sys.stdin.readline().split())
        graph[x].append(y)
        graph[y].append(x)

    print(BFS(graph, X, Y, N))
solution()

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

Categories:

Updated:

Leave a comment