글 읽기 - 11725_트리의 부모 찾기 시간초과

dmk11111 1년 전 0

<알고리즘>
a,b를 입력 받을때, 우선 둘중 어느것이 부모이고 자식인지 파악한다.
arr에 이미 존재하는것이 부모이고 나머지가 자식이 된다.
파악을 완료하면 dictionary의 child에 parent를 입력해주고, arr에도 새로 추가된 자식을 추가한다.
N-1번 반복한다 (1은 이미 루트로 존재하므로 제외함)
2부터 N까지 숫자의 부모를 출력한다

DFS,BFS로 풀어야 한다는것은 알지만 이 방법이 오히려 간단한것 같은데 계속 시간초과가 뜹니다..

해결 부탁드립니다

import sys
input=sys.stdin.readline

n=int(input())
arr=[1]
dict={}

for _ in range(n-1):
    a,b=map(int,input().split())
    
    if a in arr:
        parent,child = a,b
    else:
        parent,child = b,a

    arr.append(child)
    dict[child]=parent

[print(dict[i]) for i in range(2,n+1)]

kokosoko59 1년 전 1

dfs, bfs를 잘 쓰면 복잡도 n 만으로도 풀 수있는 문제입니다.

질문자님의 코드는 11번 줄의 조건문에서 in arr을 확인할때 n이 걸리고 전체적으로 n^2이라서 시간초과가 되는 것 같습니다.

그리고 간선이 항상 1부터 주어진다는 보장도 없기 때문에 이 코드는 틀린 답을 출력할 수도 있습니다.

이렇게 맨처음 간선이 1이 아닌 다른 두 개의 노드를 연결하는 경우, 둘 중에서 어느쪽이 parant일지 모르기 때문에 올리신 코드로는 틀릴 수 있습니다.

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

문제

문제

출처

ICPC

11725_트리의 부모 찾기 시간초과

dmk11111 1년 전 0

kokosoko59 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말