사용자 도구

사이트 도구


ps:problems:boj:11725

트리의 부모 찾기

ps
링크https://www.acmicpc.net/problem/11725
출처BOJ
문제 번호11725
문제명트리의 부모 찾기
레벨실버 2
분류

그래프, 그래프탐색

시간복잡도O(n)
인풋사이즈n<=100000
사용한 언어Python
제출기록67548 KB / 424 ms
최고기록320 ms
해결날짜2020/11/24

풀이

  • 1번 노드에서부터 전체 트리를 탐색하면서 방문하는 노드들에 대해 이전 노드를 부모 노드로 마킹하면 끝.
  • DFS/BFS 어느 것을 사용해도 상관 없다. 내 경우는 DFS를 사용.

코드

"""Solution code for "BOJ Q11725. 트리의 부모 찾기".

- Problem link: https://www.acmicpc.net/problem/11725
- Solution link: http://www.teferi.net/ps/problems/boj/11725
"""

import sys


def main():
    N = int(sys.stdin.readline())
    graph = [set() for _ in range(N)]
    for _ in range(N - 1):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        graph[u - 1].add(v - 1)
        graph[v - 1].add(u - 1)

    parent_by_node = [None] * N
    stack = [0]
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if parent_by_node[v] is None:
                stack.append(v)
                parent_by_node[v] = u + 1

    print(*parent_by_node[1:], sep='\n')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
O W W D D
 
ps/problems/boj/11725.txt · 마지막으로 수정됨: 2020/11/27 15:37 저자 teferi