[BOJ][⚪2][백준#11725] 트리의 부모 찾기

문제 출처

BAEKJOON Online Judge #11725

문제

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

입력

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

출력

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

예제

예제 1

입력

7
1 6
6 3
3 5
4 1
2 4
4 7

출력

4
6
1
3
1
4

예제 2

입력

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

출력

1
1
2
3
3
4
4
5
5
6
6

My Sol

import sys
input = sys.stdin.readline
from collections import deque

V = int(input())
tree = [[] for _ in range(V+1)]
for _ in range(V-1):
    u, v = map(int, input().split())
    tree[u].append(v)
    tree[v].append(u)

Q = deque()
Q.append(1)
p = deque()
p.extend([0]*(V+1))
p[0] = p[1]= -1

while Q:
    k = Q.popleft()
    for h in tree[k]:
        if p[h]: continue
        p[h] = k
        Q.append(h)

p.popleft()
p.popleft()
while p:
    print(p.popleft())

무향 그래프로 트리의 간선 관계를 모두 정의하고, deque에 1을 채워 1번 노드와 연결된 정점들의 p 인덱스에 1을 지정하고, deque에 넣는다. 이 과정에서 p에 값이 있는 노드라면, 이미 부모노드이므로 배제한다. 이렇게 하나씩 deque에 넣으며 p를 채워나가고, p를 모두 채워 q가 없다면 2번 노드부터 출력하면 되겠다.

결과

맞았습니다!!

모범답안

출처

import sys
from collections import deque
I=sys.stdin.readline
N=int(I())
G=[[] for _ in [0]*(N+1)]
for _ in [0]*(N-1):
    A,B=map(int,I().split())
    G[A].append(B)
    G[B].append(A)
R=[0]*(N+1)
Q=deque([1])
while Q:
    T=Q.popleft()
    for V in G[T]:
        if R[V]==0:
            R[V]=T
            Q.append(V)
print(*R[2:],sep='\n')

연산시간이 절반정도 되는 코드를 채점현황에서 가져와 분석한다. 거의 비슷한 방법이고, 슬라이싱을 사용했음에도 왜 시간이 더 빠른지 알 수가 없다. 거의 완벽히 비슷한 방법으로 풀었다.