[백준]2644: 촌수계산

dfs

문제 : 촌수계산

양방향 그래프로 쉽게 풀 수 있습니다.
주어진 두 사람의 촌수를 계산하는 문제 이기 때문에 두 사람의 순서는 상관이 없습니다.
그래서 먼저 들어온 사람을 기준으로 촌수를 계산하기로 했습니다.
이때 양방향 그래프를 사용하면 둘 중 어떤 노드부터 시작해도 결과값이 같게 나오기 때문에 양방향 그래프를 사용하여 dfs를 돌렸습니다.
방문 리스트를 만들어서 부모노드의 자식노드이면 뎁스를 하나씩 늘려가며 dfs를 도는 로직으로 작성하였습니다.
그리고 시작 노드와 연결되지 않은 노드는 0이기때문에 -1을 출력 아니면 방문값을 출력했습니다.

n = int(input())
start, end = map(int, input().split())
k = int(input())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
#양방향 그래프 
for i in range(k):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
#dfs 돌면서 방문값 갱신 
def dfs(start):
	for i in graph[start]:
		if visited[i] == 0:
			visited[i] = visited[start]+1
			dfs(i)

dfs(start)
if visited[end] == 0:
	print(-1)
else:
	print(visited[end])