99클럽 코테 스터디 8일차 TIL + DFS

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

import sys
input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
flag = False # 촌수 찾았는지 확인

for _ in range(m):
    x,y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(v, cnt):
    global flag
    visited[v] = True

    if v == b:
        flag = True
        print(cnt)

    for i in graph[v]:
        if visited[i] == False:
            dfs(i, cnt + 1)    

dfs(a, 0)
if flag == False:
    print(-1)

• x가 y의 부모라는 점에서 graph[y].append(x)를 안해도 된다고 처음에 잘못 생각했지만 양방향 관계이므로 양방향으로 추가해야한다..
• flag 변수를 이용해 촌수를 찾았는지 여부를 관리한다.
• a부터 b까지의 depth(cnt)가 답이된다.