boj 11725 : 트리의 부모찾기

문제 주소: https://www.acmicpc.net/problem/11725

난이도: tier 2

1.문제설명

• 루트없는 트리가 주어진다. 이때 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 코드를 구현해라

2.문제해결 아이디어.

• 핵심 아이디어는 노드의 부모를 기록하는 리스트를 만드는 것이다.

parent = [0 for _ in range(N+1)] #처음에는 다 0으로 초기화 한다.

3.문제접근법

• 노드간의 연결관계를 연결리스트로 받자
• 그다음 parent리스트를 재귀를 통해 업데이트 시켜주자

def DFS(start, tree, parent):
    for i in tree[start]:
        if parent[i] == 0:
            parent[i] = start
            DFS(i, tree, parent)

DFS(1, tree, parent) #1이 루트니까 1부터 시작

4.특별히 참고할 사항

• 기존의 코드를 제출해봤는데 시간초과가 발생했다.
• 시간복잡도를 고려할 때가 된거같다.
• sys.stdin.readline을 이용하자.. 꼭

5.코드구현

A.DFS 버전

#시간복잡도 통과한 코드

import sys
N = int(input())
sys.setrecursionlimit(10**9)
tree = [[] for i in range(N + 1)]
parent = [0 for _ in range(N+1)]
for _ in range(N - 1):
    n1, n2 = map(int, input().split())
    tree[n1].append(n2)
    tree[n2].append(n1)

def DFS(start, tree, parent):
    for i in tree[start]:
        if parent[i] == 0:
            parent[i] = start
            DFS(i, tree, parent)

DFS(1, tree, parent)

for i in range(2, N+1):
    print(parent[i])

#2번노드부터 DFS를 통해 1을 찾는 방법으로 했는데, 매우 비효율적이다.
#트리의 특성상 결국에는 모두 연결되어있다. 따라서 최악의 경우 O(N^2)의 시간복잡도가 발생할수도 있다.
N = int(input())
tree = [[] for i in range(N + 1)]
for _ in range(N - 1):
    n1, n2 = map(int, input().split())
    tree[n1].append(n2)
    tree[n2].append(n1)


def find_parent(tree, start):
    traced.append(start)
    #print(traced)
    for node in tree[start]:
        if node == 1:
            if traced[0] == start:
                return print(node)
            else:
                return print(traced[1])
        else:
            if node not in visited:
                visited.add(node)
                find_parent(tree, node)


for i in range(2,N+1):
    traced = []
    visited = set()
    find_parent(tree, i)

BFS 버전(훨씬 빠르다)

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n + 1)]
parent = [0 for _ in range(n + 1)]

for _ in range(n - 1):
    n1, n2 = map(int, input().split())
    tree[n1].append(n2)
    tree[n2].append(n1)

def bfs():
    q = deque([1])
    while q:
        node = q.popleft()
        for i in tree[node]:
            if parent[i] == 0:
                parent[i] = node
                q.append(i)

    return parent

bfs()

for i in parent[2:]:
    print(i)