파이썬 백준 11725번 : 트리의 부모 찾기 - DFS, BFS

문제

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

 

풀이

DFS와 BFS를 이용해서 풀 수 있다.

부모노드 결국 탐색했던 이전노드의 값이다! 탐색을 진행하면서 방문하지 않은 노드를 방문시 visited 리스트에 부모 노드의 값을 업데이트 한다. 

 

sol1) BFS

import sys
from collections import deque

def BFS(Graph,start,visited):
    queue=deque([start])
    visited[start]=1
    while queue:
        V = queue.popleft()
        for i in Graph[V]:
            if visited[i]==0:#부모노드가 정의되어있지 않은경우
                queue.append(i)
                visited[i]=V #탐색을 시작한 노드로 부모노드 정의


if __name__ == "__main__":
    n = int(sys.stdin.readline()) #n은 노드의 수
    Graph=[]
    for _ in range(n+1):
        Graph.append([])

    for _ in range(n-1):
        node1,node2=map(int,sys.stdin.readline().split(' '))
        Graph[node1].append(node2)
        Graph[node2].append(node1)
    visited=[0]*(n+1)
    BFS(Graph,1,visited)
    for i in visited[2:]:
        print(i)

 

 

sol2) DFS

import sys
sys.setrecursionlimit(1000000000)

def DFS(Graph,V,visited):
    for i in Graph[V]:
        if visited[i]==0: #부모노드가 정의되어있지 않은경우
            visited[i]=V #탐색을 시작한 노드로 부모노드 정의
            DFS(Graph,i,visited)

if __name__ == "__main__":
    n = int(sys.stdin.readline()) #n은 노드의 수
    Graph=[]
    for _ in range(n+1):
        Graph.append([])

    for _ in range(n-1):
        node1,node2=map(int,sys.stdin.readline().split(' '))
        Graph[node1].append(node2)
        Graph[node2].append(node1)
    visited=[0]*(n+1)
    DFS(Graph,1,visited)
    for i in visited[2:]:
        print(i)

 

 

🤔덧)

재귀제한을 sys.setrecursionlimit(100000)로 설정했더니 런타임에러(RecursionError)이 나왔다.

아직 제한을 어느정도로 해야하는지 잘 모르겠다..