🟩 [백준] [Python] [BFS/DFS] 2644번

🗝️ Algorithm/🟩 백준

🟩 [백준] [Python] [BFS/DFS] 2644번_촌수계산

Dbswnstjd 2022. 11. 17. 04:57

문제

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

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어

www.acmicpc.net

풀이

# 백준 2644번 문제 - 촌수계산
from collections import deque
n = int(input())
x, y = map(int, input().split())
m = int(input())
graph = [[] for i in range(n+1)]
visited = [0 for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
def dfs(x):
        for i in graph[x]:
            if visited[i] == 0:
                visited[i] = visited[x] + 1
                dfs(i)
dfs(x)
print(visited[y] if visited[y] > 0 else -1 )