[Python, 백준/11725번] 트리의 부모 찾기

---

☑️ [Python, 백준/11725번] 트리의 부모 찾기

1️⃣ 문제

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

 

2️⃣ 접근

이 문제도 DFS, BFS 중에서 하나라도 개념을 알고 있다면 큰 어려움 없이 풀 수 있는 문제다.

 

트리의 부모는 다음과 같은 조건이 만족할 수 있어야 한다.

1. 부모 Node의 Depth는 항상 탐색 Node Depth - 1을 가져야 한다.

2. 서로 인접한 관계에 있어야 한다.

 

간단하게 말해서 탐색하려는 Node의 상위에 있는 Node가 부모 Node가 된다. 

 

각 Node를 순회하면서 인접 관계에 있는 자식들을 찾고 배열에 넣어줌으로서 쉽게 해결할 수 있었다.

 

참고로 초반에는 dfs 함수와 dfs_visit 함수를 나눠서 구현했는데 메모리 초과가 발생해서 dfs 함수를 경량화 했다. 불통과한 코드도 같이 올려둔다.

 

3️⃣ 코드

# 통과한 코드
import sys
sys.setrecursionlimit(10**6)

def dfs(start_node):
    for i in graph[start_node]:
        if visit[i] == False:
            visit[i] = True
            parents[i] = start_node
            dfs(i)
    
    
if __name__ == '__main__':
    n_count = int(sys.stdin.readline())
    
    visit = [False] * (n_count + 1)
    parents = [0] * (n_count + 1)

    graph = [[] for i in range(n_count + 1)]
    for i in range(n_count - 1):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    dfs(1)
    
    for i in range(2, len(parents)):
        print(parents[i])
        
# 통과하지 못한 코드 - 메모리 초과
import sys

n_count = int(sys.stdin.readline())

graph = [[0]*(n_count + 1) for _ in range(n_count + 1)]
for i in range (n_count - 1):
    a,b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

visit = [False] * (n_count + 1)
parent_arrays = [0] * (n_count + 1)

def dfs():
    for i in range(1, len(graph)):
        for j in range(1, len(graph[i])):
            if visit[j] == False:
                dfs_visit(j)
                
def dfs_visit(node):
    global parent_arrays
    
    visit[node] = True
    
    for i in range(len(graph[node])):
        if graph[node][i] == 1 and visit[i] == False:
            dfs_visit(i)
            parent_arrays[i] = node
    
if __name__ == '__main__':
    dfs()
    for i in range(2, len(parent_arrays)):
        print(parent_arrays[i])