[dfs/백준] 11725번 : 트리의 부모 찾기

- 문제 : https://www.acmicpc.net/problem/11725

 

스스로 푼 문제다! Silver Level2 문제 

처음에 bfs로 풀었는데, 잘 안돼서 dfs로 변경 후 진행했더니 정답이 떴다. 

로직은 탐색을 하면서 v번째 리스트에 있는 원소들의 루트는 v이므로, root 리스트에 이를 입력해 주고, 

탐색 여부는 visit 안 한 원소들로만 진행한다(not visit)

 

recursionError가 발생해서 sys.setrecursionlimit(10**6)을 걸어줬다 

그리고 초반에 작성했던 bfs풀이도 정답이 떴지만, 시간이 오래 걸렸다 

 

- 정답 풀이 :

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

n=int(input())
data=[[] for _ in range(n+1)]
root=[0]*(n+1)
visit=[0]*(n+1)
visit[0]=1
visit[1]=1
for _ in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
    data[a].sort()
    data[b].sort()
    
def dfs(v):
    visit[v]=1
    for i in data[v]:
        if not visit[i]:
            visit[i]=1
            root[i]=v
            dfs(i)
 
dfs(1)
for i in range(2,n+1):
    print(root[i])

 

-BFS 풀이 

sys.stdin.readline으로 하면 안 할 때보다 시간이 1/10로 단축된다 

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

n=int(input())
data=[[] for _ in range(n+1)]
root=[0]*(n+1)
visit=[0]*(n+1)
visit[0]=1
visit[1]=1
for _ in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
    data[a].sort()
    data[b].sort()
    
def bfs(v):
    queue=deque()
    queue.append(v)
    while queue:
        x=queue.popleft()
        for i in data[x]:
            if not visit[i]:
                visit[i]=1
                root[i]=x
                queue.append(i)
bfs(1)            
for i in range(2,n+1):
    print(root[i])