[BOJ 2644] 촌수계산 (Python)

www.acmicpc.net/problem/2644

2644번: 촌수계산

n=int(input())
a,b=map(int, input().split())
graph=[[] for _ in range(n+1)]
visited=[False]*(n+1)
m=int(input())
result=-1
for _ in range(m):
    i,j=map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

def dfs(a, b, count):
    global result
    if a==b:
        result=count
    visited[a]=True
    for i in graph[a]:
        if visited[i]==False:
            dfs(i,b,count+1)
    return result

print(dfs(a,b,0))

DFS를 이용했다.

기준점 A 를 기준으로 count를 1씩 늘려 탐색한 뒤, 탐색 대상이 목표인 B와 같다면 result 변수에 count를 저장한다.

모든 재귀의 호출이 끝난 뒤 result를 리턴한다. 

 

---

 

BFS로 하면 더 효율적으로 짤 수 있을 듯.

visited[사람수] 배열 만들어서 1씩 추가해주면.. 메모리 절약할듯.. 괜히 DFS 써서 재귀 이용해서 좀 힘들어졌었다..

BFS로 짠것도 조만간 올릴것..!!