[Python] SW Expert Academy #1248 공통조상

📚문제: #1248 공통조상(D5)

전체 코드

# 1248. 공통조상
from copy import deepcopy

# 서브 트리의 크기
global st_size

# DFS 알고리즘(부모 to 자식)
def DFS_p(s):

    global st_size
    
    # 현재 노드 방문처리
    visited_p[s] = True
    
    # 서브 트리의 크기 1 추가
    st_size += 1
    
    # 이웃 노드 탐색
    for neighbor in graph_p[s]:
        
        # 방문 하지 않은 노드는 DFS로 탐색
        if not visited_p[neighbor]:
            
            DFS_p(neighbor)        

global array

# DFS 알고리즘(자식 to 부모)
def DFS_c(s):
    
    global array
    
    # 현재 노드 방문처리
    visited_c[s] = True
    
    # 현재 노드 추가
    array.append(s)
    
    # 이웃 노드 탐색
    for neighbor in graph_c[s]:
        
        if not visited_c[neighbor]:
            
            DFS_c(neighbor)

# 테스트 케이스의 수
T = int(input())

# 테스트 케이스
for t in range(1, T+1):
    
    # 정점 개수, 간선 개수, 두 개의 정점 번호가 주어진다.
    V, E, n1, n2 = map(int, input().split())
    
    # 간선 정보가 주어진다.
    edge_info = list(map(int, input().split()))

    # 부모 to 자식 그래프 (1 ~ V)
    graph_p = [[] for _ in range(V+1)]
    visited_p = [False] * (V+1)
    
    # 자식 to 부모 그래프 (1 ~ V)
    graph_c = [[] for _ in range(V+1)]
    
    st_size = 0
    
    # 간선 정보 반영
    for i in range(0, 2*E, 2):
        
        # 부모, 자식    
        edge1, edge2 = edge_info[i], edge_info[i+1]
        
        # 부모 to 자식 그래프에 반영
        graph_p[edge1].append(edge2)
        
        # 자식 to 부모 그래프에 반영
        graph_c[edge2].append(edge1)
        
    # 공통조상을 찾는다.
    array = []
    visited_c = [False] * (V+1)
    
    DFS_c(n1)
    n1_array = deepcopy(array)
    
    # 초기화
    array = []
    visited_c = [False] * (V+1)
    
    DFS_c(n2)
    n2_array = deepcopy(array)
    
    n1_array = n1_array[::-1]
    n2_array = n2_array[::-1]
    
    for node in n1_array:
        
        if node in n2_array:
            
            ancestor = node
            
    # 공통조상을 루트로 하는 서브 트리의 크기를 구하자
    DFS_p(ancestor)
    
    # 답 출력
    print("#{} {} {}".format(t, ancestor, st_size))

아이디어

부모 → 자식을 탐색하는 DFS, 자식 → 부모를 탐색하는 DFS를 각각 따로 구현해준다.