[백준] 2644번 촌수계산

💡문제접근

• 기본적인 BFS/DFS 문제였다. 만약 방문한 횟수가 없다면 두 사람의 친척 관계가 전혀 없는 촌수이므로 -1을 출력하고 만약 0보다 큰 값이라면 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력하면 된다.

💡코드(메모리 : 34104KB, 시간 : 60ms)

from collections import deque
import sys
input = sys.stdin.readline

def BFS(graph, start):
    queue = deque()
    queue.append(start)
    while queue:
        start = queue.popleft()
        for i in graph[start]:
            if not visited[i]:
                visited[i] = visited[start] + 1
                queue.append(i)

n = int(input().strip())
a, b = map(int, input().strip().split())
m = int(input().strip())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().strip().split())
    graph[x].append(y)
    graph[y].append(x)
visited = [0] * (n+1)
BFS(graph, a)
if visited[b] > 0:
    print(visited[b])
else:
    print(-1)

💡소요시간 : 22m