[Python] 백준 #11725- 트리의 부모 찾기

문제

---

11725번: 트리의 부모 찾기

코드

---

My answer

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

def bfs(idx):
    Q=deque()
    Q.append(idx)
    visited[idx]=1
    
    while Q:
        a=Q.popleft()
        for i in graph[a]:
            if(visited[i]==0):
                parents[i]=a
                Q.append(i)
                visited[i]=1
    return 0

n=int(input())

graph=[[] for _ in range(n+1)]
visited=[0 for i in range(n+1)]
parents=[0 for i in range(n+1)]

for i in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
bfs(1)
print(*parents[2:])

Another answer

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

N = int(input())

Tree = [[] for _ in range(N+1)]
Parents = [0 for _ in range(N+1)]

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

def DFS(start, tree, parents) :
    for i in tree[start] :
        if parents[i] == 0 :
            parents[i] = start
            DFS(i, tree, parents)

DFS(1, Tree, Parents)

for i in range(2, N+1) :
    print(Parents[i])

풀이

---

우선 나는 bfs로 해결했다. 동일한 방법으로 bfs 함수를 생성하고, 돌면서 부모 노드번호를 parents라는 배열에 저장했다. 다른 분들 코드를 보고 생각해보니, 굳이 parents란 배열을 생성하지 않고 그냥 visited에 1대신 부모 노드 번호를 넣으면 메모리도 아낄 수 있을 것이다. 

another answer은 dfs로 푼 코드를 가져왔다.