[백준] 실버1/파이썬 - 11726 트리의 부모 찾기

 

문제

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

 

문제 설명

각 노드 별로 연결된 두 정점의 정보를 바탕으로 각 노드 별 부모 노드를 출력하는 문제이다.

문제에서는 2번 노드부터 출력하도록 되어있다.

 

입력값

n : 노드의 개수

트리 상에 연결된 n-1개의 연결된 두 정점의 정보

 

출력값

2부터 n까지 노드들의 부모 노드 정보 출력한다.

 

 

작성 답안

'''
@ No: 11725
@ Title: 트리의 부모 찾기
@ key Point: 재귀

@ 입력값:
    - n : 노드의 개수
    - 트리 상에 연결된 두 개의 정점 정보 n-1 개

@ 출력값 : 각 노드의 부모 노드 번호 출력
'''


import sys
sys.setrecursionlimit(10**6)

# n = 7
# graph = [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]]

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


visited = [0] * (n+1)

def dfs(node):
    # 부모 > 자식 노드로 탐색
    for i in graph[node]:
        if visited[i] == 0:
            visited[i] = node # 부모 노드 탐색 후 방문 처리
            dfs(i)

dfs(1)

for j in range(2, n+1):
    print(visited[j])

 

 

설명

 

처음에 트리에서 노드 별 연결된 정보를 어떻게 저장하느냐에 대해서 고민을 하였다.

2차원 배열로 해서 연결된 노드에 대해서는 1로 표시하는 방식으로 할까 고민하였다가, 해당 경우에는 100이상이 되면 메모리 부족으로 인해 다른 방법을 고안하였다.

 

정점의 연결 정보를 저장한 다음에, 부모 노드에서 자식노드로 탐색을 시작하였다.

해당 자식노드가 아직 방문하지 않은 경우에 방문처리를 하고 해당 자식노드를 부모 노드라 생각하고 다시 탐색을 진행하여

dfs 방식을 사용하였다.

 

그 이후에 방문 처리 정보를 저장한 리스트를 정답으로 출력하는 방식으로 구성하였다.