백준 3584 가장 가까운 공통 조상 파이썬 풀이, 반례

난이도 : 골드4

풀이일 : 2403052

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

3584번: 가장 가까운 공통 조상

---

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

---

1차 시도 오답

import sys
from collections import deque


def sol(n, m):
    # n의 자식들의 자식들을 찾아나가며 m 찾기
    queue = deque([n])
    while queue:
        x = queue.popleft()
        for y in tree[x]:
            # m 발견 시 return
            if y == m:
                return print(n)
            queue.append(y)

    # n 대신 n 부모 노드로 재귀 호출
    if parent[n]:
        sol(parent[n], m)


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

for _ in range(T):
    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)
        parent[B] = A

    a, b = list(map(int, sys.stdin.readline().split()))

    sol(a, b)

틀린 이유

• m이 n의 부모일 경우를 고려하지 못함

---

반례

입력	1 2 1 2 2 1
출력	1

---

정답 코드

import sys
from collections import deque


def sol(n, m):
    # m이 n의 부모라면 m 출력
    if parent[n] == m:
        return print(m)

    # n의 자식들의 자식들을 찾아나가며 m 찾기
    queue = deque([n])
    while queue:
        x = queue.popleft()
        for y in tree[x]:
            # m 발견 시 return
            if y == m:
                return print(n)
            queue.append(y)

    # n 대신 n 부모 노드로 재귀 호출
    sol(parent[n], m)


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

for _ in range(T):
    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)
        parent[B] = A

    a, b = list(map(int, sys.stdin.readline().split()))

    sol(a, b)

코드 변화

• sol 함수에 m이 n의 부모이면, 출력하게 하는 부분 추가
• 재귀 호출 시, 루트 노드인지 확인하던 조건 제거

코드 구성

• sol 함수
  • m이 n의 부모라면, m 반환 후 종료
  • deque에 n을 넣고, n의 모든 자식들의 자식들을 탐색
    • 만약, 자식을 탐색 중 m을 발견하면 n 반환 후 종료
  • n 대신 parent[n]을 넣어 함수 재귀 호출
• tree : 각 노드가 자식으로 갖는 노드들을 기록하기 위한 이차원 배열
• parent : 각 노드의 부모를 기록하기 위한 배열
  • 0 번째 인덱스를 제외하고, parent[n]이 0이라면 루트노드
• 입력 받는 동안 tree, parent를 기록
• 가장 가까운 공통 조상을 구해야 하는 두 수에 대해 sol 실행

---

느낀점

• deque 문제를 주구장창 풀었던 때 때문인지 재밌게 풀었다. 틀렸을 땐 안재밌었지만.
• 반례를 찾아보지 말고 스스로 생각해보는 습관을 길러야 하는데 자꾸 반례부터 찾아보게 되어서 문제다.
• 제출 시간은 00:00:08로 찍혔지만, 어쨌건 나는 5일 문제로 분류해야지 그래도 안 풀려다가 한 문제 푸니까 되게 뿌듯하네ㅎㅎ