사실 문제를 봤을때 촌수를 계산하라지만 노드간의 부모가 하나뿐인 전형적인 그래프라서 bfs를 돌리면 풀수 있겠단 생각이 들었어요
근데 이것이 코딩테스트다에서 find_parent를 이용해 푸는 문제를 봤던 생각이 나서
처음엔 부모 경로를 찾아서 만나는 경로의 거리를 찾는식으로 작성했었는데
n = int(input())
a, b = map(int, input().split())
d = [i for i in range(n + 1)]
for _ in range(int(input())):
x, y = map(int, input().split())
d[y] = x
def findParent(n, depth, path):
if n == d[n]: return n, depth
path.append(n)
return findParent(d[n], depth + 1, path)
pathA, pathB = [], []
parentA, depthA = findParent(a, 0, pathA)
parentB, depthB = findParent(b, 0, pathB)
if parentA != parentB:
print(-1)
else:
print(len(set(pathA+pathB)))
결국은 이런식으로는 어떻게해도 정답을 받을수 없었어요
왜 그럴까 생각하다가 꼭 최종으로 가지 않아도 중간지점에서 겹치는 가족이 있을수겠단 생각이 들었습니다
근데 이 코드에서 pathA+pathB는 두 a b가 최종부모에서 만날때의 최단거리라 정답이 안나오는게 당연했어요
그래서 오늘 새로 코드를 작성했는데
n = int(input())
a,b = map(int, input().split())
d = [*range(n + 1)]
for _ in range(int(input())):
x, y = map(int, input().split())
d[y] = x
pathA=[]
t=a
while True:
pathA.append(t)
if t==d[t]: break
t=d[t]
pathB=[]
t=b
while True:
pathB.append(t)
if t==d[t] or t in pathA: break
t=d[t]
if pathB[-1] in pathA:
print(len(pathA[:pathA.index(pathB[-1])]+pathB)-1)
else:
print(-1)
이렇게 a의 최종 부모까지의 경로를 구한다음 b의 부모를 찾을때 a랑 겹치는 부분이 있으면 b 경로찾기를 멈추고
b가 겹치는 곳까지 가는 경로랑 a가 겹치는곳까지 가는 경로를 합쳐서 길이를 구해줬습니다
그럼 a와 b가 포함된 경로 리스트의 길이가 구해지는데 a와 b중 어떤 한곳에서 출발한다고 하면 자신은 셀필요가 없기 때문에 길이 -1을 해주면 정답!!
