[백준/파이썬] 11725번 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 11725번 문제
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

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

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

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

코드

import collections
import sys


class Node:
    def __init__(self, parent, data):
        self.parent = parent;
        self.data = data;
        self.children = collections.deque([])
        
n = int(sys.stdin.readline())
node_dict = {1: Node(None, 1)}

class Tree:
    def __init__(self):
        self.tree = node_dict[1];

    def push(self, a, b):
        node_dict[b] = Node(node_dict[a], b)
        node_dict[a].children.append(node_dict[b])

                
    def result(self):
        outs = []
        for i in range(2, n+1):
            outs.append(node_dict[i].parent.data)
        print("\n".join(map(str, outs)))

tree = Tree()
tree.push

graph = {i:[] for i in range(1, n+1)}
checked = [False]*(n+1)
queue = collections.deque([])

for _ in range(1, n):
    a, b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

queue.append(1)
while queue:
    cur = queue.popleft()
    if checked[cur]:
        continue
    checked[cur] = True
    while graph[cur]:
        tmp = graph[cur].pop()
        if checked[tmp]:
            continue
        queue.append(tmp)
        tree.push(cur, tmp)

tree.result()

설명

핵심은 구현 관점에서 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.를 만족하도록 로직을 구성하는 것입니다.

코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.

경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.

---

• 백준 문제풀이 전체 목록 보기

---