S2 11725. 트리의 부모 찾기

문제 보기 :  11725번: 트리의 부모 찾기

---

문제

• 정답률 : 42%

 

---

작성 코드

import sys
input = sys.stdin.readline

# 입력 처리
T = int(input())  # 노드의 개수 입력
graph = [[] for _ in range(T+1)]  # 노드의 연결 정보를 저장할 그래프 초기화

# 트리 구조 입력
for _ in range(T-1):  
    a, b = map(int, input().split())  # 연결된 두 노드 입력
    graph[a].append(b)  # 양방향 그래프 구성
    graph[b].append(a)

mama = [0] * (T+1)  # 각 노드의 부모를 저장할 리스트 초기화

from collections import deque  # BFS를 위한 deque 사용

# BFS 함수 정의
def bfs(graph):
    dd = deque([1])  # 루트 노드(1)에서 탐색 시작
    while dd:
        now = dd.popleft()  # 현재 탐색 중인 노드
        for node in graph[now]:  # 연결된 모든 노드 탐색
            if mama[node] == 0:  # 부모가 아직 설정되지 않은 노드라면
                mama[node] = now  # 현재 노드를 부모로 설정
                dd.append(node)  # 다음 탐색 대상으로 추가

bfs(graph)  # BFS를 통해 각 노드의 부모를 구함

mama = mama[2:]  # 2번 노드부터 출력해야 하므로 슬라이싱
print(*mama, sep='\n')  # 각 노드의 부모를 줄바꿈으로 출력

---

풀이

노드 개수(T)와 트리의 간선 정보를 입력받아 양방향 그래프로 구성했다.

그리고 mama 리스트는 각 노드의 부모 정보를 저장하는 리스트이며,
BFS 알고리즘으로 부모 노드가 설정되지 않은 노드를 발견하면 현재 노드를 부모로 설정하도록 bfs 함수를 짰다.

최종적으로는 mama 리스트 원소 중 2번째 값부터 출력한다.