[PYTHON] 백준 11725 - 트리의 부모 찾기

성능 요약

메모리: 68244 KB, 시간: 332 ms

분류

그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색

문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

---

아이디어, 문제풀이

• 각 노드의 부모를 구하는 문제이기에, 그래프 탐색이 다음단계로 들어갔을때 각 노드에 부모노드를 저장하는 기능을 넣어야 한다.
• 문제에서는 visit에 start를 넣는 방식으로 진행했다.

---

TROUBLE SHOOTING

• 이 문제를 푼 이후부터, dfs문제는 앞으로 항상 stack을 사용해야겠다 생각했다. 재귀문으로 코드를 구성하면 코드 자체가 깔끔해지긴 하지만, 깔끔해 지는 만큼 구현도 어렵고, 이해도 어렵다. 실제로 쉬운문제에 속하는데, 재귀문을 구현하는데에 정말 어려웠다.

• 매번 놓치는 부분이 있는데, 재귀함수를 사용할 경우 python으로 제출 해야지만 정답으로 나온다.

  sys.setrecursionlimit(10**6)

  재귀문의 제한을 늘려주는 코드도 잊지말자!
  

• 구현 자체의 난이도는 어렵지 않았다.

---

코드

#https://www.acmicpc.net/problem/11725
#트리의 부모 찾기
#11725

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())

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

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    # graph.sort([a])

# print(graph)

visit = [0] * (n+1)

def dfs(graph, start, visit):

    # visit[start] = 1

    for i in graph[start]:
        if visit[i] == 0:
            visit[i] = start  
            dfs(graph, i, visit)
        else:
            continue

    # print(visit)

dfs(graph, 1, visit)

for i in range(2,len(visit)):
    print(visit[i])