[백준] 11725 파이썬(python) : 트리의 부모 찾기 - (dfs, bfs)

11725번: 트리의 부모 찾기

 

 

bfs풀이)

from collections import deque
import sys
n = int(input())
graph = [ [] for _ in range(n+1) ]
for _ in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visit = [False] * (n+1)

def bfs():
    q = deque()
    q.append(1)
    while q:
        v = q.popleft()
        for i in graph[v]:
            past = v
            if not visit[i]:
                visit[i] = v #1
                q.append(i)
bfs()
for i in range(2, n+1): #2
    print(visit[i])

 

#1 : 방문한 노드의 부모노드 저장

#2 : 2번 노드부터 자신의 부모노드 출력

 

bfs풀이2) 23.01.12(목)

import sys
from collections import deque
n = int(sys.stdin.readline().strip())
graph = [ [] for _ in range(n+1) ]
for _ in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visit = [False]*(n+1)
arr_root = [ [] for _ in range(n+1) ]
def bfs(v):
    q = deque()
    q.append(v)
    visit[v] = True
    while q:
        v = q.popleft()
        for i in graph[v]:
            if visit[i] == False:
                visit[i] = True
                q.append(i)
                arr_root[i].append(v) #1
bfs(1)
for i in range(2, len(arr_root)):
    print(*arr_root[i])

 

#1 : 새로운 리스트에 자신의 루트 노드의 번호를 삽입

 

나의 dfs풀이) - 22.08.08

import sys
sys.setrecursionlimit(10**5) #1
n = int(sys.stdin.readline())
graph = [ [] for _ in range(n+1) ]
for _ in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visit = [False]*(n+1)
visit[1] = True #2
res = [] #3
def dfs(v):
    for i in graph[v]:
        if not visit[i]:
            visit[i] = True
            res.append((v, i)) #4
            dfs(i)
dfs(1)
res.sort(key=lambda x : x[1]) #5
for i in res:
    print(i[0]) #6

 

#1 : 10^5(십만)까지 재귀해제

#2 : 루트 노드인 1 방문처리

#3 : 부모노드와 자식노드를 함께 저장할 리스트 생성

#4 : 자식노드를 저장할때 부모노드도 같이 저장

#5 : 자식노드 순으로 정렬

#6 : 차례대로 부모노드를 출력

 

10^6, 10^9, 10^3, 10^4으로 모두 재귀해제를 했지만 메모리초과나 런타임에러가 발생했지만 10^5으로 하니 운이 좋게 맞았다. 여기서 성공하지 못했으면 싹 다 지우고 bfs로 다시 풀뻔했다.

 

앞으로도 메모리초과 나오는 dfs코드는 10^5으로 맞추고 해봐야겠다.