[Baekjoon] 25516_거리가 k이하인 트리 노드에서 사과 수확하기

Silver II

문제(출처: https://www.acmicpc.net/problem/25516)

---

< 거리가 k이하인 트리 노드에서 사과 수확하기 >

 

문제 풀이 

 

bfs를 활용하여 문제를 해결했다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _25516_ { // 거리가 k이하인 트리 노드에서 사과 수확하기
	static ArrayList<ArrayList<Integer>> arr;
	static int apple[], k, result;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		int tree[] = new int[n];

		arr = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			arr.add(new ArrayList<>());
			tree[i] = -1;
		}

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(bf.readLine());
			int p = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			arr.get(p).add(c);
			tree[c] = p;

		}

		int start = 0;
		for (int i = 0; i < n; i++) {
			if (tree[i] == -1) {
				start = i;
				break;
			}
		}

		apple = new int[n];
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			apple[i] = Integer.parseInt(st.nextToken());
		}

		result = 0;

		bfs(start);

		System.out.println(result);
	}

	private static void bfs(int start) {
		Queue<int[]> queue = new LinkedList<>();
		result += apple[start];
		queue.add(new int[] { start, 0 });

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int num : arr.get(temp[0])) {
				result += apple[num];
				if (temp[1] + 1 < k) {
					queue.add(new int[] { num, temp[1] + 1 });
				}
			}
		}
	}
}

 

Main

변수)
n : 정점 개수
k : 거리
tree : 루트 구하기 위해 부노 노드 저장
arr : 자식 정점 저장
p : 부모 정점 번호
c : 자식 정점 번호
start : 루트 노드
apple : 사과의 수 저장
result : 수확할 수 있는 사과 개수
queue : [정점 번호, 거리]

 

- 정점의 수(n), 거리(k) 입력

- 부모 정점 번호(p), 자식 정점 번호(c) 입력받아 저장

- 부모 노드를 저장한 배열을 탐색하여 값이 -1이면 루트 노드이므로 -1인 값을 찾음

- 각 노드의 사과의 수를 저장 (apple)

- bfs 함수 호출

- 수확할 수 있는 사과 개수(result) 출력

 

bfs

- queue에 저장 [정점 번호, 거리]

- queue가 빌 때까지 반복

: 부모 노드에 해당하는 자식 노드를 찾아 해당하는 사과의 수를 result에 더함

: 거리가 k보다 작으면 queue에 저장

---

---