[Baekjoon/🥈SilverⅡ] 11725: 트리의 부모 찾기

Intro

👩 문제는 bfs, dfs 두가지 방식으로 해결할 수 있다.

• 두 방식의 공통점은 노드를 탐색하는 과정에서 직전 노드를 부모노드로 설정하는 것이다.

Algoritm👩‍💻: dfs

#21.01.27
#11725: 트리의 부모 찾기

import sys
sys.setrecursionlimit(10**6)

def dfs(n):
  for i in lst[n-1]:
    if parent[i] == 0:
      parent[i] = n # 직전 노드를 부모로 지정!
      dfs(i)

N = int(sys.stdin.readline())
lst = [[] for _ in range(N)]
parent = [0 for _ in range(N+1)]

for _ in range(N-1):
  n1, n2 = map(int, sys.stdin.readline().split())
  lst[n1-1].append(n2)
  lst[n2-1].append(n1)

dfs(1)

for i in parent[2:]:
  print(i)

Algorithm👨‍💻: bfs

#21.01.27
#11725: 트리의 부모 찾기

import sys

def bfs():
  global check
  queue = [1]
  while queue:
    p = queue.pop(0)
    for i in lst[p-1]:
      if parent[i] == 0:
        parent[i] = p # 직전 노드를 부모로 설정!
        queue.append(i)
  

N = int(sys.stdin.readline())
lst = [[] for _ in range(N)]
parent = [0 for _ in range(N+1)]

for _ in range(N-1):
  n1, n2 = map(int, sys.stdin.readline().split())
  lst[n1-1].append(n2)
  lst[n2-1].append(n1)

bfs()

for i in parent[2:]:
  print(i)

이번 포스팅은 여기서

끝!! ~(˘▾˘~)