[백준, 파이썬, 2644번] 촌수계산

풀이

• 처음 접근한 방식은 단순히 자식에서 부모를 찾으면 된다는 것 하나로
• 간단하게 접근하여 제시된 예제는 모두 통과 했지만 
• 계속해서 12%에서 틀렸다고 나오기에 
• 어떤 이유인지 조사했을 때 발견한 것으로
• 첫 번째는 조사해야하는 a,b가 있을 때 
• a가 b의 부모이던지, 그 반대의 경우에 대한 조건을 찾을 수 있었으며
• 두 번째로는 사실 계속 고민했을 때 찾지 못해 
• 다른 게시글로 알게 된 정말 간단한 것으로
• 더 높은 숫자가 부모가 되는 조건으로
• 어떤 방식으로 해결해야 좋을지 고민한 결과
• 그냥 단순히 부모에 연결된 자식 li를 하나씩 탐색하는 방법을 택하였으며
• 여기에 bfs를 적용하여 각 노드에서 하나씩 모두 탐색하여
• a와b 모두 연결된 것 중, 가장 적은 촌수를 가진 값을 도출하여 해결할 수 있도록 함.

 

import sys

from collections import deque

input = sys.stdin.readline

n = int(input())

li = [[] for _ in range(n+1)]

a,b = map(int,input().split())

for _ in range(int(input())):

    x,y = map(int,input().split())

    li[x].append(y)

result = -1

for i in range(1,n+1):

    if li[i]:

        hap = 0

        q = deque([[i,0]])

        s_a,s_b = False, False

        while q:

            num,cnt = q.popleft() 

            if num == a:

                s_a = True

                hap += cnt

            elif num == b:

                s_b = True

                hap += cnt

            if s_a and s_b: break

            for j in li[num]: q.append([j,cnt+1])

        if s_a and s_b:

            if result == -1: result = hap

            else: result = min(result, hap)

print(result)