공통조상(SW Expert Academy, SWEA)

난이도 : D5

문제번호 : 1248

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD&categoryId=AV15PTkqAPYCFAYD&categoryType=CODE

SW Expert Academy

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

이진 트리에서 임의의 두 정점의 공통 조상 중 가장 가까운 것을 찾으려 한다. 예를 들어, 아래의 이진 트리에서 정점 8과 13의 공통 조상은 정점 3와 1 두 개가 있다. 이 중 8, 13에 가장 가까운 것은 정점 3이다. 정점 3을 루트로 하는 서브 트리의 크기(서브 트리에 포함된 정점의 수)는 8이다. 임의의 이진 트리가 주어지고, 두 정점이 명시될 때 이들의 공통 조상 중 이들에 가장 가까운 정점을 찾고, 그 정점을 루트로 하는 서브 트리의 크기를 알아내는 프로그램을 작성하라. 입력에서 주어지는 두 정점이 서로 조상과 자손 관계인 경우는 없다. 위의 트리에서 예를 든다면 두 정점이 “11과 3”과 같이 주어지는 경우는 없다.

 

입력

가장 첫줄은 전체 테스트케이스의 수이다. 10개의 테스트 케이스가 주어진다. 두 줄이 하나의 테스트 케이스가 되며, 따라서 전체 입력은 20줄로 이루어진다. 각 케이스의 첫줄에는 트리의 정점의 총 수 V와 간선의 총 수 E, 공통 조상을 찾는 두 개의 정점 번호가 주어진다 (정점의 수 V는 10 ≤ V ≤ 10000 이다).  그 다음 줄에는 E개 간선이 나열된다. 간선은 간선을 이루는 두 정점으로, 항상 “부모 자식” 순서로 표기된다. 위에서 예로 든 트리에서 정점 5와 8을 잇는 간선은 “5 8”로 표기되고, 절대로 “8 5”와 같이 표기되지는 않는다. 간선이 입력되는 순서는 정해져 있지 않다. 입력에서 이웃한 수는 모두 공백으로 구분된다. 정점의 번호는 1부터 V까지의 정수이며, 전체 트리에서 루트가 되는 정점은 항상 1번으로 표기된다. 부모 정점이 자식 정점보다 항상 번호가 작은 것은 아니다. 즉, 40번 정점이 20번 정점의 부모가 될 수도 있다. 이 문제에서 자식 정점이 부모 정점의 왼쪽 자식인지 오른쪽 자식인지는 중요하지 않다.

출력

총 10줄에 10개의 테스트 케이스 각각에 대한 답을 출력한다. 각 줄은 테스트 케이스의 번호를 의미하는 ‘#x’로 시작하고 공백을 하나 둔 다음 답을 기록한다. 답은 공통조상 중 가장 가까운 것의 번호, 그것을 루트로 하는 서브 트리의 크기를 뜻하는 2개의 정수로 구성된다. 이 두 정수는 공백으로 구분한다.

예시

입력	출력
10 13 12 8 13 1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 10 6 11 11 13 10 9 2 10 1 2 1 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 ...	#1 3 8 #2 1 10 ...

---

2. 문제풀이

그래프 문제인데 공통의 조상을 찾는 문제이다. 연결리스트를 이용해 그래프를 표현했는데, 이때 부모와 자식을 표현하기 위해서 뒤에따로 표시를 해주었다. 연결된 노드가 부모노드라면 1, 자식노드라면 0으로 표시하였다. 특정노드 2개를 주고 공통노드를 찾으라고 하는데 dfs를 이용하여 탐색하였다. 주어진 노드와 연결된 노드를 찾으며 부모노드라면(1번이라면) set에 해당노드를 추가하고 딕셔너리에 해당노드는 몇번째 부모이다를 표시한 뒤에 재귀하는 형식을 취하였다. 2개의 모드의 모든 부모노드를 찾았다면 교집합을 이용하여 공통으로 보유하는 부모노드만 찾았다. 이후 공통된 노드를 딕셔너리에 넣어보면서 제일빠른 노드를 찾도록 하였다. 마지막으로 공통조상 노드를 찾았다면, 재귀함수를 이용하여 자기 밑에있는(자식노드)를 모드찾아가며 카운팅하였다.

---

3. 소스코드

# D5 1248 공통조상
 
# 자기 위의 노드가 누구누구 있는지 확인하는 함수
def find_parent(n, idx, count=0):
    # 트리를 돌면서 체크하자
    for i in tree[idx]:
        # i[1]이면 부모라는 뜻이다.
        if i[1]:
            # 부모노드를 찾았으니까 set에 추가하고
            parents[n].add(i[0])
            # 몇번째 만에 찾았는지 모르니까 순서도 저장하고
            order[n][i[0]] = count
            # 다시 돌린다.
            find_parent(n, i[0], count+1)
 
# 트리의 크기를 찾기위한 함수
def find_tree(n):
    global tree_size
    # 반복문 돌려보자
    for i in tree[n]:
        # 자식노드만 찾으면 되니까 i[0]이 0인거 찾는다.
        if not i[1]:
            # 찾았으면 트리사이즈 하나늘리고
            tree_size += 1
            # 다시 돌린다
            find_tree(i[0])
 
 
for t in range(int(input())):
    # 결과 출력용 변수
    # 시작하는 노드 포함이니까 1로 셋팅
    tree_size = 1
    my_parent = -1
    # 입력받고
    V, E, A, B = map(int, input().split())
    temp = list(map(int, input().split()))
    # 필요한 변수 만들어주고
    # 공통찾기용
    parents = {A:set(), B:set()}
    # 순서찾기용
    order = {A:{}, B:{}}
 
    # 그래프 리스트화
    tree = [[] for _ in range(V+1)]
    for i in range(0, len(temp), 2):
        a, b = temp[i], temp[i+1]
        tree[a].append((b, 0))
        tree[b].append((a, 1))
    # 자기 부모노드 찾고
    find_parent(A, A)
    find_parent(B, B)
    # 교집합으로 후보군 정리하고
    candidatekey = list(parents[A] & parents[B])
    distance = 999
    # 제일 가까운 조상 찾기
    for i in candidatekey:
        if order[A][i] < distance:
            distance = order[A][i]
            my_parent = i
    # 트리 크기 찾아주고
    find_tree(my_parent)
    #결과출력
    print('#{} {} {}'.format(t+1, my_parent, tree_size))