백준 11437 LCA 파이썬 풀이

난이도 : 골드3

풀이일 : 2403122

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

11437번: LCA

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 0% 시간초과

import sys
from collections import deque


def find(n, m):
    if parent[n] == m:
        return print(m)

    temp = deque([n])
    while temp:
        i = temp.popleft()
        for ni in tree[i]:
            if ni != parent[i]:
                if ni == m:
                    return print(n)
                temp.append(ni)

    find(parent[n], m)


N = int(sys.stdin.readline())
tree = [[] for _ in range(N + 1)]
parent = [0] * (N + 1)

for _ in range(N  - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    tree[a].append(b)
    tree[b].append(a)

M = int(sys.stdin.readline())

queue = deque([1])
while queue:
    x = queue.popleft()
    for nx in tree[x]:
        if nx != parent[x]:
            parent[nx] = x
            queue.append(nx)

for _ in range(M):
    a, b = list(map(int, sys.stdin.readline().split()))
    find(a, b)

코드 구성

• tree : 주어지는 연결 정보 저장
• parent : 연결정보 입력 후 루트 1부터 부모 노드 기록
• queue : 부모 노드를 기록하기 위해 사용되는 queue
• find : n의 모든 자식 노드 ni에 대해서 queue인 temp에 ni 추가, ni 가 m인 경우, n 출력 후 반환
  • 반환되지 않았다면, parent[n], m을 인자로 재귀 호출

틀린 이유

• 재귀 호출로 인해 검사했던 모든 노드들을 다시 검사하는 불필요한 연산 반복

---

2차 시도 오답 -> 0% 시간초과

import sys
from collections import deque


def find(n, m):
    if parent[n] == m:
        return print(m)
    visited = [0] * (N + 1)
    visited[n] = n
    temp = deque()
    temp.append(n)
    while temp:
        i = temp.popleft()
        for ni in tree[i]:
            if not visited[ni]:
                if ni != parent[i]:
                    visited[ni] = visited[i]
                    if ni == m:
                        return print(visited[i])
                    temp.append(ni)
                else:
                    visited[ni] = ni
                    temp.append(parent[i])
    return


N = int(sys.stdin.readline())
tree = [[] for _ in range(N + 1)]
parent = [0] * (N + 1)

for _ in range(N  - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    tree[a].append(b)
    tree[b].append(a)

M = int(sys.stdin.readline())

queue = deque([1])
while queue:
    x = queue.popleft()
    for nx in tree[x]:
        if nx != parent[x]:
            parent[nx] = x
            queue.append(nx)

for _ in range(M):
    a, b = list(map(int, sys.stdin.readline().split()))
    find(a, b)

코드 변화

• 재귀호출 대신 BFS 방식으로 visited 기록
• temp 에서 popleft한 요소 i에 대해 연결된 모든 ni 조사
  • 만약 ni가 i의 자식노드라면, visited[ni]에 i 기록
  • 만약 ni가 i의 부모노드라면, visited[ni]에 ni 기록
• ni가 m이라면, 출력 및 반환

틀린 이유

• 시간복잡도 O(N + MN)이 제한에 걸린 것 같다. 입력되는 쿼리 수 M이 많을 때 비효율적인 코드
• 다시 보니 m이 i의 부모요소일때도 처리를 해주고 위에 if문은 빼는 등 정리 필요

---

최종 코드 정답 -> python 시 93% 시간초과

import sys
from collections import deque

# 공통 조상 찾기 함수
def find(n, m):
    # 깊이 맞추기
    while depth[n] != depth[m]:
        if depth[n] > depth[m]:
            n = parent[n]
        else:
            m = parent[m]
    # 깊이가 같다면 공통 조상까지 역행
    while n != m:
        n, m = parent[n], parent[m]

    return print(n)


N = int(sys.stdin.readline())
# 연결 정보 저장
tree = [[] for _ in range(N + 1)]
# 부모 노드 기록
parent = [0] * (N + 1)
# 깊이 기록
depth = [0] * (N + 1)

# 입력
for _ in range(N  - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    tree[a].append(b)
    tree[b].append(a)

# 트리 부모 정리
queue = deque([1])
while queue:
    x = queue.popleft()
    for nx in tree[x]:
        if nx != parent[x]:
            parent[nx] = x
            depth[nx] = depth[x] + 1
            queue.append(nx)

M = int(sys.stdin.readline())

# 공통조상 찾을 두 수
for _ in range(M):
    a, b = list(map(int, sys.stdin.readline().split()))
    find(a, b)

코드 변화

• depth : 부모 노드 기록 시, 해당 노드의 깊이를 저장해 줄 배열
• find : 최소 공통 부모 찾기 함수
  • 1. 두 노드의 깊이가 다르면, 깊이가 같아질 때까지 깊이가 깊은 노드를 부모요소로 재할당
  • 2. 두 노드의 깊이가 같다면, 두 노드를 직접 비교
  • 3. 두 노드가 다르다면, 같아질때까지 두 노드 모두 부모 요소로 재할당
  • 4. 두 노드가 같아지면 둘 중 아무거나 출력 후 반환

---

느낀점

• 알고리즘이 엄청 재미있었다. 이런 식으로 이런 문제를 풀 수 있는 게 신기하고 재밌는 느낌. 내일도 비슷한 문제를 풀어봐야지
• 마지막 방식도 python으로 제출했더니 93%에서 시간초과로 오답처리가 되어서 pypy로 제출해봤더니 통과했다.