[파이썬] 2644번 '촌수계산' 문제 풀이

[파이썬] 2644번 '촌수계산' 문제 풀이

예가 다음과 같이 나오는 경우

9 7 3 7 1 2 1 3 2 7 2 8 2 9 4 5 4 6

인접 리스트는 [[], [2, 3], [1, 7, 8, 9], [1], [5, 6], [4], [4], [2], [2], [2]]로 표현되며,

자식을 트리의 시작노드, 부모를 자식노드로 놓고 순회하면서 자식노드(부모)에 도착하는 경우 부모노드(자식)가 갖는 촌수에 +1을 하는 방식으로 문제를 해결합니다.

dfs를 이용한 풀이

def dfs(v): visited[v] = True for i in graph[v]: if not visited[i]: res[i] = res[v] + 1 dfs(i) n=int(input()) A,B=map(int,input().split()) m=int(input()) graph=[[] for _ in range(n+1)] visited = [False] * (n + 1) res=[0]*(n+1) for _ in range(m): a,b=map(int,input().split()) graph[a].append(b) graph[b].append(a) dfs(A) if res[B]>0: print(res[B]) else: print(-1)

bfs를 이용한 풀이

from collections import deque def bfs(s): queue=deque([s]) visited[s]=True while queue: v=queue.popleft() for i in graph[v]: if not visited[i]: queue.append(i) res[i]=res[v]+1 visited[i]=True n=int(input()) A,B=map(int,input().split()) m=int(input()) graph=[[] for _ in range(n+1)] visited = [False] * (n + 1) res=[0]*(n+1) for _ in range(m): a,b=map(int,input().split()) graph[a].append(b) graph[b].append(a) bfs(A) if res[B]>0: print(res[B]) else: print(-1)

문제 출처: https://www.acmicpc.net/problem/2644

from http://lbdiaryl.tistory.com/212 by ccl(A) rewrite - 2021-11-23 18:27:10