[백준 11725번] 파이썬 - 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

# 조건

• 루트 없는 트리가 주어진다.
• 이 때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램 작성

 

입력

• 첫 줄에 노드의 개수 N (2<=N<=100,000)이 주어진다.
• 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

# 접근 방법

• 트리의 정점을 tree 리스트에 받아준 후 리스트에 추가해준다.
• parent 리스트를 만들어 준 후 dfs 실행
• 루트 노드인 1을 시작정점으로 하여 tree에 기록되어 있는 node 살펴보기
• 방문하지 않았다면 -> node로 들어가기
•  
  이후 parent 리스트의 node인덱스에 시작 정점 기록해주면 된다.
  • parent 리스트의 정점 값이 0이 아니라면 -> 방문한 것

 

dfs 풀이

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
def dfs(start):  
    parent=[0] * (N+1)  
    parent[start] = 1  
    stack = [start]  
    while stack:  
        node = stack.pop()  
        for i in tree[node]:  
            if not parent[i]:  
                stack.append(i)  
                parent[i] = node  
  
    print(*parent[2:], sep='\n')  
  
  
N = int(input())  
tree = [[] for _ in range(N+1)]  
  
for i in range(N-1):  
    a, b = map(int, input().split())  
    tree[b].append(a)  
    tree[a].append(b)  
  
  
dfs(1)

 

 

bfs 풀이

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
def bfs(start):  
    parent=[0] * (N+1)  
    parent[start] = 1  
    q = deque()  
    q.append(start)  
    while q:  
        node = q.popleft()  
        for i in tree[node]:  
            if not parent[i]:  
                q.append(i)  
                parent[i] = node  
  
    print(*parent[2:], sep='\n')  
  
  
N = int(input())  
tree = [[] for _ in range(N+1)]  
  
for i in range(N-1):  
    a, b = map(int, input().split())  
    tree[b].append(a)  
    tree[a].append(b)  
  
  
bfs(1)