Tree_00_트리의 부모 찾기(11725)
Tree00트리의 부모 찾기(11725)
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
풀이
- 1번 노드를 제외한 나머지 노드의 부모 노드를 찾아 출력하는 문제
- 트리의 루트를 1이라고 임의로 가정했으므로 DFS 혹은 BFS를 1번 노드부터 진행한다.
- 처음 방문하는 노드마다 그 노드를 탐색한 직전의 노드 번호를 기록해준 뒤 출력하면 된다.
코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
tree = [[] for _ in range(n+1)]
par = [-1]*(n+1)
for _ in range(n-1):
a,b = map(int,input().split())
tree[a].append(b)
tree[b].append(a)
def dfs(n):
for i in tree[n]:
if par[i] == -1:
par[i] = n
dfs(i)
dfs(1)
for i in range(2,n+1):
print(par[i])
배운 것
코멘트
Author And Source
이 문제에 관하여(Tree_00_트리의 부모 찾기(11725)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@angel_eugnen/Tree00트리의-부모-찾기11725
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
- 1번 노드를 제외한 나머지 노드의 부모 노드를 찾아 출력하는 문제
- 트리의 루트를 1이라고 임의로 가정했으므로 DFS 혹은 BFS를 1번 노드부터 진행한다.
- 처음 방문하는 노드마다 그 노드를 탐색한 직전의 노드 번호를 기록해준 뒤 출력하면 된다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
tree = [[] for _ in range(n+1)]
par = [-1]*(n+1)
for _ in range(n-1):
a,b = map(int,input().split())
tree[a].append(b)
tree[b].append(a)
def dfs(n):
for i in tree[n]:
if par[i] == -1:
par[i] = n
dfs(i)
dfs(1)
for i in range(2,n+1):
print(par[i])
Author And Source
이 문제에 관하여(Tree_00_트리의 부모 찾기(11725)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Tree00트리의-부모-찾기11725저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)