[백준 문제풀기] #2644번 - 촌수계산 문제 with Python

 

💁🏻‍♀️ How do I  thought

dfs나 bfs로 풀어야할 것 같다는 느낌은 직감적으로 들었다. 

하지만 각 x,y를 입력받아 2차원 배열에 양방향으로 넣어서 풀어야한다는 생각까지밖에 그치지 않았다. 

 

🙆🏻‍♀️ How to solve

Dfs 방식으로 구현하였다.

촌수를 계산해야하는 서로 다른 번호를 c,d라고 한다. 

먼저 graph에 부모 자식관계를 양방향으로 넣어주고, 자식(c)에서 부모 노드(d)로 가는 방법으로 재귀탐색을 해준다. 

dfs를 재귀적으로 탐색하여 재귀 깊이가 깊어질때마다 num의 값을 +1씩 해주고, 현재 노드의 번호가 부모노드의 번호와 같아질 때 num 값을 출력해준다. 

 

 

💻 Code

import sys
from collections import deque

n = int(sys.stdin.readline())
c,d = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
result = []

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# dfs
def dfs(v, num):
  num += 1
  visited[v] = True

  if v == d:
    result.append(num)

  for i in graph[v]:
    if not visited[i]:
      dfs(i, num)

dfs(c, 0)

if len(result) == 0:
  print(-1)
else:
  print(result[0] -1)