개발일지/Algorithm
백준 - 11725 트리의 부모 찾기 [DFS][BFS]
E-room
2023. 11. 5. 12:20
728x90
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
1. 문제 요약
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
2. 파이썬
2 - 1. BFS
백준 - 2606 바이러스 [BFS]
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어
e-room.tistory.com
2 - 2. 코드
N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
a, b = map(int, input().split())
tree[a].append(b)
tree[b].append(a)
parents = [0] * (N+1)
parents[1] = 1
q = [1]
while q:
node = q.pop()
for next in tree[node]:
if not parents[next]:
parents[next] = node
q.append(next)
print(*parents[2:], sep='\n')
3. 자바
3 - 1. DFS
백준 - 2606 바이러스 [DFS] 자바 백준 1위
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어
e-room.tistory.com
3 - 2. 코드
static List<Integer>[] tree;
static int[] parents;
private static void solution(int node) {
for (int next : tree[node]) {
if (parents[next] == 0) {
parents[next] = node;
solution(next);
}
}
}
4. 전체 코드
728x90