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

내용과 무관한 사진입니다(어그로) - 출처: 엔트립

정말 오랜만에 블로그에 다시 돌아왔네요! 

문제풀이도 쉽지 않고 해서 꾸준히 풀이 글을 적어가면서 오답노트도 하고,

재미도 다시 붙여보려 해요!

-문제

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

촌수 계산 문제입니다!

 

- 내 풀이

문제 이름만 들어봐도 트리 연결 구조를 분석해야 하겠다는 생각이 드는데요.

저는 트리가 익숙하지도 않고 해서 리스트 활용한 간단 연산으로 풀었어요.

 

a, b의 촌수를 구한다고 하면 결국은 둘을 연결하는 간선의 개수를 구하라는 건데, 이거를 리스트를 활용해서 직관적으로 구할 수 있다고 생각했어요.

 

a_p, b_p 리스트의 역할

a와 b를 포함한 각각의 부모를 차례대로 대입한 리스트에요.

먼저 자식들에게 하나의 부모만 존재한다는 조건이 있었기에 쉽게 시도할 수 있었어요.

그래서 a의 부모가 1, 1의 부모가 4라고 한다면 

a_p = [a, 1, 4] 가 되는 거죠.

 

a_p, b_p 리스트를 활용해서..

만약 a_p 와 b_p에 공통으로 등장하는 숫자가 있다면 이는 a와 b의 공통 조상을 의미하는거죠.

이를 이용해 a에서 공통조상 까지의 촌수를 인덱스의 차로 구해주고, 공통조상부터 b까지의 촌수를 또 인덱스의 차로 구해서 더해주면 끝! 이네요.

 

- 내 소스코드 

설명한 내용을 간단하게 구현해보면

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

rel = int(input())
j ={}
for _ in range(rel):
    p, s = map(int, input().split())
    j[s] = p

b_p = [b]    
while True:
    if b not in j.keys():
        break
    b_p.append(j[b])
    b = j[b]
    
a_p = [a]    
while True:
    if a not in j.keys():
        break
    a_p.append(j[a])
    a = j[a]


cnt = 0
target = 0
for i in range(len(a_p)):
    if a_p[i] in b_p:
        cnt = i
        target = a_p[i]    
        break
    else:
        cnt += 1
else:
    print(-1)
    quit()
result = cnt + b_p.index(target)
print(result)

 

이렇게 나오는 거죠

 

- DFS

물론 트리 혹은 그래프 구조니까 그래프에 부모, 자식 관계를 넣어주고 깊이우선탐색으로 해결해도 될거에요~