[ 백준 / 골드2 / 파이썬 Python ] 2233번 - 사과나무

링크 : https://www.acmicpc.net/problem/2233

2233번: 사과나무

 

코드

---

n = int(input())
tree = list(map(int,str(input())))
x,y = map(int,input().split())

a,b = 0,0
inOut = [[0,0] for _ in range(n+1)]
parent = [0] * (n+1)
depth = [0] * (n+1)
prev, last = 0, 0
for i in range(1,2*n+1):
    status = tree[i-1]
    if status == 0: # 0은 도착지
        last += 1
        parent[last] = prev
        depth[last] = depth[prev]+1
        prev = last
        inOut[last][0] = i
    else: # 1은 출발지
        inOut[prev][1] = i
        prev = parent[prev]

for i in range(1,n+1):
    if x in inOut[i]:
        a = i
    if y in inOut[i]:
        b = i

while depth[a] != depth[b]:
    if depth[a] > depth[b]:
        a = parent[a]
    else:
        b = parent[b]

while a != b:
    a = parent[a]
    b = parent[b]

print(*inOut[a])

 

풀이

---

이 코드에서 헷갈릴 수 있는 부분은 정점의 번호와 간선의 번호이다. 길을 잃지 않도록 잘 구분해서 해결해야 한다.

 

 

• a와 b :  입력받은 x와 y가 가리키는 정점의 번호를 담을 변수.
• inOut : 트리의 구조를 파악하기 위해 이진수로 정점을 가리키는 간선의 번호를 저장하는 배열.
• parent : 정점마다의 부모노드를 저장하는 배열.
• depth : 트리구조에서 정점의 깊이를 저장하는 배열.
• prev, last : prev는 현재 탐색을 이어가는 나의 위치이고 last는 가장 마지막 정점의 번호이다.

간선의 상태가 0이면 한 번도 방문한 적 없는 노드에 방문하기 때문에 가장 마지막 정점의 번호 + 1을 한다.

해당 정점의 부모는 간선을 처리하기 전에 위치했던 prev 정점이다.

도착지(last)에 간선의 번호를 저장한다.

간선의 상태가 1이면 출발지(prev)에 간선의 번호를 저장한다. 또한 다시 왔던 길을 돌아가기 때문에 부모정점으로 이동한다.

 

x와 y가 가리키는 정점의 번호를 구한다.

 

이 문제의 핵심인 LCS알고리즘이다.

두 정점의 깊이와 부모노드를 알고 있을 때, 두 정점의 최단거리에 위치한 공통부모를 구하는 방법이다.

먼저 두 정점의 깊이를 똑같이 맞춰준다. 똑같은 깊이임에도 두 정점이 다르다면 두 정점이 같아질 때까지 동시에 부모노드로 이동시킨다.

계속해서 부모노드로 이동하다보면 결국 같은 부모노드에서 만나거나 루트노드에서 만나게 된다.