글 읽기 - 두 정점이 같은 트리인지 탐색하는 로직이 숨은 반례에서 틀렸습니다.

betaf1sh 3년 전 0

Good Bye, BOJ 2020! 의 C번 문제를 해설 영상을 힌트로 풀었습니다. 아래 임베드한 유튜브 플레이어를 재생하면 바로 C 번 풀이를 볼 수 있습니다.

두 정점이 같은 트리에 위치해 있으면 1을(True) 출력하고, 다른 트리에 위치하면 사이클로 판단해서 2를(False) 출력하라는 로직을 query 의 go 라는 DFS 함수로 표현했습니다.

아래 사진을 예시로 (4, 5) 는 동일한 트리에 속하고, (6, 1) 과 (6, 4) 은 다른 트리에 속합니다. 사이클 위의 노드를 루트로 생각하시면 편합니다.

백준에 제출 후 약 20초 시점의 숨은 테스트 케이스에서 틀렸으며, 소스 코드 전문은 외부 링크에서 참고 부탁드립니다.

def query(paths: Dict[int, set], queries: List[Query]):
    # ...
    def go(query: Tuple[int, int]):
        node, goal = query
        if node == goal:
            return True

        if len(paths[node]) == 1:
            return go((tuple(paths[node])[0], goal))

        if not branchs.get(node):
            return False

        return goal in branchs[node]

    return tuple(map(go, queries))


def test_query():
    assert query(paths, [(2, 4), (4, 5)]) == (True, True)
    assert query(paths, [(1, 4), (7, 4)]) == (False, False)

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

문제

문제

출처

ICPC

두 정점이 같은 트리인지 탐색하는 로직이 숨은 반례에서 틀렸습니다.

betaf1sh 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말