[BOJ] Python 백준 촌수계산(2644)

 

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

 

전형적인 특정 값 사이의 dfs 깊이 구하기 문제

import sys
input = sys.stdin.readline

N = int(input())
target1, target2= map(int,input().split())
visited = [False] * (N+1)
s = [[] for _ in range(N+1)]
M = int(input())

for _ in range(M):
    u,v = map(int,input().split())
    s[u].append(v)
    s[v].append(u)

chk = False
def dfs(n, start, end):
    global chk
    visited[start] = True


    if start == end:
        print(n)
        chk = True
        exit()

    for i in s[start]:
        if not visited[i]:
            dfs(n+1, i, end)

dfs(0,target1, target2)

if not chk:
    print(-1)

 

 

 

회고.

bfs로 푸는게 나을지 dfs로 푸는게 나을지 아직 고민하는 것을 봐서 아직 더 열심히 해야할 듯 싶다