[파이썬]baekjoon 2644: 촌수계산

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

2644번: 촌수계산

---

다익스트라나, 여러 방법이 있겠지만 나같은 경우 dfs로 풀었다.

 

촌수를 타고 들어가는걸 직관적으로 확인할 이중배열을 만들고,

 

타고 들어가며 알고자 하는 사람과 몇촌인지 확인하면 됨!

n = int(input())
arr = [[0]*(n+1)for _ in range(n+1)]
f, c = list(map(int,input().split()))
m = int(input())
# 2중배열로 만들어줌
for i in range(m):
    x,y = map(int,input().split())
    arr[y][x] = 1
    arr[x][y] = 1

answer = -1
visit = [[0]*(n+1)for _ in range(n+1)]
def dfs(level,f):
    global answer
    if f == c:
        answer = level
        return

    for i in range(n+1):

        if arr[f][i] == 1:
            if visit[f][i] == 1: continue
            visit[f][i] = 1
            visit[i][f] = 1
            dfs(level+1,i)

dfs(0,f)
print(answer)