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
'개발일지 > Algorithm' 카테고리의 다른 글
| 프로그래머스 - 뉴스 클러스터링 [자바] (0) | 2023.11.28 |
|---|---|
| 백준 - 1991 트리 순회 [Tree] (0) | 2023.11.01 |
| 프로그래머스 - 짝지어 제거하기 [Stack] (0) | 2023.10.30 |
| 백준 - 2606 바이러스 [BFS] (1) | 2023.10.28 |
| 백준 - 2606 바이러스 [DFS] 자바 백준 1위 (1) | 2023.10.28 |
