[백준/2644/파이썬] 촌수계산

소스코드

N = int(input())

A, B = map(int, input().split())

M = int(input())

graph = [[] for _ in range(N+1)]

visited = [False] * (N+1)

result = [0] * (N+1)

for _ in range(M):

  x, y = map(int, input().split())  

  graph[x].append(y)

  graph[y].append(x)

def dfs(v):

    visited[v] = True

    for i in graph[v]:

        if not visited[i]:

            result[i] = result[v] + 1

            dfs(i)

dfs(A)

if result[B]>0:

    print(result[B])

else:

    print(-1)

알고리즘

dfs를 사용해서 풀면 간단하게 풀 수 있는 문제인데요

1. 입력된 사람들간의 관계를 graph로 list에 저장해준다.

2. visited는 방문을 했으면 True이고 방문을 안했으면 다음 dfs에서 True로 바뀐다.

(시작이 7이면

1. graph[7] == [2]

2. graph[2] == [1,7,8,9]

3. graph[1] == [2,3]

4-1. graph[2] => visited

4-2. graph[3] = [1]

5. graph[1] => visited )

 

3. 그리고 graph에 있는 list를 가지고 방문을 하고 1번 방문할때마다 1씩 촌수가 늘어난다.

(ex. 7 ->2 ->1->3 이면 3촌)

4. result에 있는 촌수를 return하는데 만약 0이면  -1을 return한다.