[Python] 2644번 촌수계산

문제

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

풀이과정

x와 y의 촌수를 나타내야한다.

x 부터 시작하여 y가지 도달할 수 있으면 출력하고 아니라면 -1을 출력한다.

y에 도달하면 여태까지 탐색할 때 카운트 되던 값(떨어져 있는 거리)를 출력한다.

전부 탐색했는데, 원하는 값이 없으면 -1을 출력한다.

import sys
input = sys.stdin.readline

n = int(input())
x, y = map(int, input().split())
g = [[] for _ in range(n+1)]

m = int(input())
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

visited = [False for _ in range(n+1)]
result = []

def dfs(x, cnt):
    visited[x] = True
    cnt += 1
    for i in g[x]:
        if i == y:
            result.append(cnt)
        elif visited[i] == True:
            continue
        dfs(i, cnt)

dfs(x, 0)

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

바이러스 문제와는 다르게 전부 탐색했을 때 아무 관계가 없으면 -1을 출력하는 것이 관건이였다.