글 읽기 - 요즘 도와달라는 글을 너무 쉽게 쓰는 거 아닌가 반성하고 있습니다만 도와주세요..

jiyolla 3년 전 1

이번에는 부분부분 Unit test? 비슷한 것도 나름했는데, 어디서 틀렸는지 모르겠네요...

큰 과정은

1. DFS순회 한 번 하면서 parent, depth만들기.

2. dp로 parent_2tothe만들기. parent_2tothe[i][j]는 j의 2^i번째 parent임.

3. parent_2tothe를 이용해서 log2(depth[])시간에 작동하는 parent_n()만들기. parent_n(i, j)는 j의 i번째 parent. 0번째 parent는 자신.

4. parent_2tothe를 이용해서(parent_n()로 쓰면 코드는 더 깔금하겠지만 python이 느린 거 같아서) find_LCA()만들기. find_LCA(a, b)는 a, b가 같지 않지만 같은 depth를 가진 경우에 말그대로 LCA를 찾아줌

이번에는 생각보다 코드가 제 개인적인 생각에는 나름 잘 정리되었다고 생각해서, 부분 테스트도 중간에 잘 되어서 그런지,

그래서 더 빨리 어디서 틀린지 모르겠다는 절망감이 확 밀려오고, 지금 이례적으로 Debugging한 지 1시간도 안 됐는데 이렇게 도움!글을 올립니다.

import sys
import math


def solve():
    read = sys.stdin.readline
    n = int(read())

    # 자, 트리가 주어지는데, 부모 관계는 불명
    # 단순하게 parent리스트만 만들고 싶은데, 그러려면 좀 손을 봐야됨
    # parent만들었다고 치자.
    # 10만개의 쿼리가 들어옴. 한 쿼리가 대충 log시간 안에 해결해야 돼
    # parent_2tothe[][]만들어
    # parent_2tothe[i][j]는 j의 2^i번째 parent, i = 0~필요한만큼
    # 그럼 쿼리가 들어올 때, 먼저 한놈 빠르게 끌어올려, 음 parent에 depth정보도 넣어야 됨
    # 끌어오릴는데 최대 log n시간, 그담에 같은 레벨의 두 노드에 대해서 parent달라지는 시작을 찾아냄
    # 이것도 log n 시간 안에 가능, 그러면 log n시간 안에 1개쿼리 처리 가능하네. 구현.

    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = map(int, read().split())
        adj[a].append(b)
        adj[b].append(a)

    parent = [None] * (n + 1)
    depth = [None] * (n + 1)
    stack = [(1, 0)]
    parent[1] = 1
    depth[1] = 0
    max_depth = 0
    while stack:
        cur_node, cur_depth = stack.pop()
        if cur_depth > max_depth:
            max_depth = cur_depth
        for child in adj[cur_node]:
            if child != parent[cur_node]:
                parent[child] = cur_node
                depth[child] = cur_depth + 1
                stack.append((child, cur_depth + 1))
    max_power = math.floor(math.log2(max_depth))
    parent_2tothe = [[None] * (n + 1) for _ in range(max_power + 1)]
    for node in range(1, n + 1):
        parent_2tothe[0][node] = parent[node]
    for power in range(1, max_power + 1):
        for node in range(2, n + 1):
            if depth[node] >= (1 << power):
                parent_2tothe[power][node] = parent_2tothe[power - 1][parent_2tothe[power - 1][node]]

    def parent_n(n, x):
        if n == 0:
            return x
        biggest_power_under = math.floor(math.log2(n))
        next_n = n - (1 << biggest_power_under)
        return parent_2tothe[biggest_power_under][parent_n(next_n, x)]

    # a, b are expected to on the same depth
    def find_LCA(a, b):
        for power in range(max_power + 1):
            if parent_2tothe[power][a] == parent_2tothe[power][b]:
                if power == 0:
                    return parent[a]
                return find_LCA(parent_2tothe[power - 1][a], parent_2tothe[power - 1][b])

    print_buf = []
    for _ in range(int(read())):
        a, b = map(int, read().split())
        a, b = (a, b) if depth[a] > depth[b] else (b, a)
        a = parent_n(depth[a] - depth[b], a)
        if a == b:
            print_buf.append(f'{a}')
        else:
            print_buf.append(f'{find_LCA(a, b)}')
    print('\n'.join(print_buf))


solve()

seico75 3년 전 3

jiyolla 3년 전 0

아!!!!

그렇네요...역시나 find_LCA에서 문제가 있었네요...하...

아니 이걸 왜 생각못했지?ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 얼탱이 없네...

반성하겠습니다...

find_LCA의 테스트를 가장 적게 했고, 확신도 제일 덜하기 했는데, 진짜 여기서 문제가 있었군요.

다음에는 좀 더 확실하게 입력의 모든 범위를 고민했는지 생각해볼게요 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

요즘 도와달라는 글을 너무 쉽게 쓰는 거 아닌가 반성하고 있습니다만 도와주세요..

jiyolla 3년 전 1

seico75 3년 전 3

jiyolla 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말