11725. 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

 

✔ 유형 : DFS

✔ 문제 풀이: 해당 노드와 연결된 노드들의 부모는 해당 노드라는 점을 이용해 배열에 자신의 부모 노드 번호를 저장한다.

 

백준의 테스트 케이스를 예시로 들어 설명하자면,

테스트 케이스의 연결리스트를 그래프로 나타내면 위와 같다.

 

위와 같은 방법으로 계속 DFS를 돌리면 아래와 같이 부모 리스트가 채워진다.

 

 

⬇️문제

import sys
input=sys.stdin.readline # input함수 바꾸기
sys.setrecursionlimit(10**5)
# input 
N = int(input())

Graph = {i: [] for i in range(1, N+1)}

for i in range(N-1):
    u, v = map(int, input().split())
    
    Graph[u].append(v)
    Graph[v].append(u)
    
    
parents = [0] * (N - 1)  # 부모 테이블 초기화
visited = [False] * (N + 1)  # 방문 여부 체크
   
def DFS(node):
    global visited
    global parents
    visited[node] = True
    for next in Graph[node]:
         if not visited[next]:
            parents[next-2] = node #자식과 연결되면 현재노드가 이자식의 부모임.
            DFS(next)
            
    return
        
DFS(1)

for p in parents:
    print(p)