백준 알고리즘 - 11725 - 트리의 부모 찾기

문제

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

---

입력

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

---

출력

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

 

 

---

접근법

예제 입력을 보면 첫번째 줄에 전체 노드의 개수와

두번째 줄부터 시작해서 연결된 두개의 노드가 주어진다.

그 두개의 노드 중 하나는 부모노드이고 하나는 자식노드이다.

 

여러가지 두개의 노드가 주어지지만 둘 중 어느 노드가 부모인지 아는 방법은 

주어진 두개의 노드 중에 중복된 노드가 나온다면 그 노드는 부모노드이다.

자식 노드가 두개의 부모노드를 가질 수 없기 때문이다.

 

부모노드인지 확인하는 것은 스택을 하나 만들어서 확인해주면 된다.

스택 안에 똑같은 노드가 들어간다면 그 노드는 부모노드가 아니므로 부모노드에서 빼준다.

---

코드

n = int(input())
tree = [[] for i in range(n+1)] # 트리에 담을 노드

for i in range(n-1):
    a,b = list(map(int, input().split()))
    tree[a].append(a)
    tree[b].append(b)
    
q = [1]
ans = {} 
check = [False for i in range(n+1)]

while len(q)>0:
    parent=q.pop(0)
    for i in tree[parent]: 
        if not check[i]:
            ans[i] = parent
            q.append(i)
            check[i]=True

for i in range(2,n+1):
    print(ans[i])