[백준] 11437 LCA

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

공통의 부모를 찾기 위하여 DFS 탐색을 이용하였습니다.

처음에 DFS 탐색을 루트 노드부터 시작하여 아래 노드로 진행하였고, 해당 노드까지 진행하며 지나친 노드들을 리스트로 기록하였습니다.

위의 작업을 통해 각 노드별로 바로 위 부모부터 루트노드까지 경로가 기록되어 있었습니다.

그 이후 비교할 두 노드의 경로를 가져와 한 노드의 경로에서 요소를 하나씩 가져와 다른 노드 경로에 포함되는지 여부로 공통 부모를 확인하였습니다.

한 번만 DFS탐색을 진행하고, 두 노드의 부모를 찾을때는 기록된 경로들만 가져와 공통 요소를 찾았기 때문에 적은 시간이 소요되었지만, 각 노드별로 모든 부모의 경로를 기록하였기 때문에 메모리 초과가 발생하였습니다.

 

시간이 조금 더 소요되더라도 메모리 문제를 해결하기 위하여 DFS탐색으로 각 노드의 바로 위 부모 노드만 기록하였습니다.

그 이후 두 노드를 비교할때마다 부모 노드들을 탐색하며 공통의 부모를 탐색하였습니다.

PyPy3를 이용하여 테스트를 통과하였으나 꽤 오랜 시간이 소요 되어 개선이 필요하였습니다.

이때, 각 노드의 트리 높이를 구하여 추가적으로 기록하는 방식을 알게 되었고, 비교할때 트리의 높이를 동일시한 이후, 부모를 탐색하며 동일한지 여부를 판단하는 방식을 이용하였습니다.

2) 알고리즘

• DFS

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def set_parents():
    stack = [0]                                     # DFS 탐색 위한 스택
    visited[0] = 1                                  # 루트 노드 방문처리
    level[0] = 0                                    # 루트 노드 레벨 0

    while stack:
        node = stack.pop()
        for next in linked[node]:                   # 해당 노드와 연결된 노드 탐색
            if not visited[next]:                   # 방문 하지 않은 노드만
                visited[next] = 1
                parents[next] = node                # 연결된 노드의 부모는 현재 노드
                level[next] = level[node] + 1       # 연결된 노드의 레벨은 현재 노드 레벨 + 1
                stack.append(next)                  # 다음 탐색을 위한 노드 추가

def solution(a, b):
    while level[a] != level[b]:                     # 비교하는 두 노드의 레벨이 다르면
        if level[a] < level[b]:                     # B 노드가 레벨이 더 높으면 (루트로 부터 더 멀다면)
            b = parents[b]                          # B 노드 레벨 낮추기
        else:                                           
            a = parents[a]                          # A 노드 레벨 낮추기

    while a != b:                                   # 레벨이 같은데, 두 노드가 서로 다르다면
        a = parents[a]                              # 각각 부모 노드 가져오기
        b = parents[b]

    return a                                        # A와 B가 동일하므로 공통 부모 노드

N = int(sys.stdin.readline())                       # 노드의 개수
linked = [[] for _ in range(N)]                     # 노드의 연결 관계
parents = [-1] * N                                  # 각 노드의 부모 노드 번호
level = [-1] * N                                    # 각 노드의 트리 레벨(높이)
visited = [0] * N                                   # 노드 탐색 여부

for _ in range(N-1):                                # 노드들 연결 관계를 정리
    a, b = map(int, sys.stdin.readline().split())
    linked[a-1].append(b-1)
    linked[b-1].append(a-1)

set_parents()                                       # 루트 노드를 시작으로 탐색

M = int(sys.stdin.readline())                       # 비교할 노드들의 개수

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    print(solution(a-1, b-1) + 1)                   # 두 노드의 공통 부모 찾기

---

🔗 문제 링크

- https://www.acmicpc.net/problem/11437

11437번: LCA

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다