백준 11725 트리의 부모 찾기 파이썬 문제풀이 (python 트리)

 

문제 보러가기

 

 

백준 트리의 부모 찾기 파이썬 문제풀이

이 문제는 트리의 연결 정보를 주었을 때 

루트를 1로 정하고 나머지 노드의 부모노드를 구하는 문제이다.

 

문제는 연결하는 정보를 주었을 때

루트가 1이라는 것을 전제로 하고 주지 않는 다는 점이다.

 

다른 노드에서 1로 연결하는 부분이 있으면 1의 부모가 생기는 셈인데.

루트가 1이라면 부모에서 자식으로 연결되는 방식으로 입력되는게 아니라는 것이다.

 

이에 대해서 해결하는 방법은 단방향으로 연결하는게 아니라.

양방향으로 연결하는 방법을 사용하는 것이다. 

 

양방향으로 연결하면 우려되는 점은, 부모에서 자식으로 내려가는게 아니라

자식에서 부모로 올라가는 경우가 생길 수 있는데.

 

이건 노드의 visit를 확인함으로써 해결한다. 

 

정답 코드 

n = int(input())

graph = [[] for _ in range(n+1)]
parent = [0 for _ in range(n+1)]

for _ in range(n-1):
    a,b = map(int, input().split())

    graph[a].append(b)
    graph[b].append(a)

def recur(node, pre):

    parent[node] = pre

    for nxt in graph[node]:
        if nxt == pre:
            continue
        recur(nxt,node)

recur(1,0)

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

graph를 양방향으로 연결하고,

재귀 과정에서는 루트에서부터 내려가며 1번 이후 노드의 부모들을 기록한다.

 

부모에서 자식으로 내려가면서 재귀를 하기 때문에,

이전 노드인 pre가 부모 노드에 해당한다.

 

이때 양방향에서 주의할 점은 이전 노드인 pre로 돌아가지 않도록 하는 것이다. 

즉 nxt가 pre node가 되지 않고 자식의 방향으로 가도록 제한해주면 된다. 

 

런타임 에러?

재귀할 수 있는 한계 설정이 부족한 것 같다.

 

import sys
sys.setrecursionlimit(100000)
n = int(input())

graph = [[] for _ in range(n+1)]
parent = [0 for _ in range(n+1)]

for _ in range(n-1):
    a,b = map(int, input().split())

    graph[a].append(b)
    graph[b].append(a)

def recur(node, pre):

    parent[node] = pre

    for nxt in graph[node]:
        if nxt == pre:
            continue
        recur(nxt,node)

recur(1,0)

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

문제는 재귀 횟수의 부족이었다. 

만 번 정도로 바꿔주니 통과했다. 

 

부모를 구한 마찬가지의 방법으로 자식노드 또한 구할 수 있을 것이다.