[코딩테스트] 백준 촌수계산 파이썬(python)

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

2644번: 촌수계산

n = int(input())
start, target = map(int, input().split())
m = int(input())
graph = {i : [] for i in range(1, n+1)}
for _ in range(m):
  p, c = map(int, input().split())
  graph[p].append(c)
  graph[c].append(p)
visited ={node : False for node in graph}

result = []
def dfs(v, count):
  if v == target:
    result.append(count)
  count += 1
  visited[v] = True
  nodes = graph[v]
  for node in nodes:
    if not visited[node]:
      dfs(node, count)

dfs(start, 0)

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

저는dfs로 문제를 해결하였습니다.

먼저 주어진 예제를 활용하여 graph는 아래와 같습니다.

첫번째 예제에서 시작노드은 7, 마지막노드은 3입니다.

아래과 같이 두사람의 촌수를 확인하려면 시작노드부터 마지막노드까지의 그래프의 깊이를 확인하면 됩니다.

작성한 dfs 함수를 확인해보면 count 변수로 그래프가 깊어질수록 count를 증가시키는 것을 볼 수 있습니다.

그리고 현재노드 v가 마지막노드 target가 같아진다면 result 리스트에 현재까지의 그래프의 깊이 count를 저장합니다.

두 사람의 관계가 있다면 result의 크기가 0이 아닐것입니다.

하지만 두사람의 관계가 없다면 그래프는 다음과 같을 것이며 result의 크기가 0일것입니다.

• 두사람의 관계가 없는 경우가 바로 두번째 예제입니다. 시작노드8, 마지막노드 6입니다.

따라서 result의 크기가 0이라면 -1을 반환하고 result의 크기가 0이 아니라면 저장되어있는 result[0](count)를 반환합니다.