[Python] 2644번 촌수계산

✏️ 문제

 

문제 파악

같은 알고리즘의 문제 중 11725번 트리의 부모 출력 문제가 생각난 .. 매우 비슷함

인접리스트를 활용하면 쉽게 풀 수 있다!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

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

n = int(input())
a, b = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1) 

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

def bfs(v):
  q = deque([v]) 
  visited[v] = 1 
    
  while q:
    node = q.popleft()

    for neighbor in graph[node]:
      if visited[neighbor] == 0:
        visited[neighbor] = visited[node] + 1
        q.append(neighbor)

bfs(a)
if visited[b] != 0:
  print(visited[b] - 1)  # -1로 정확한 촌수 출력
else:
  print(-1)

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS