[G2] 백준 1135번 뉴스 전하기 C++ 트리, 깊이 우선 탐색, 그리디 알고리즘, 정렬

리뷰

 

https://www.acmicpc.net/problem/1135

오일러 탐색 경로로 풀릴까 싶었는데 병렬 처리 + 그리디함이 필요해서 DFS + 정렬로 풀었다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• edges : 인접 리스트를 저장할 벡터 배열

 

함수

1. dfs

int dfs(int cn) {
	if (edges[cn].empty()) return 0;

	vector<int> times;
	for (int nn : edges[cn]) {
		times.push_back(dfs(nn));
	}
	
	sort(times.begin(), times.end(), greater<int>());
	int mx = 0;
	for (int i = 0; i < times.size(); ++i) {
		mx = max(mx, times[i] + i + 1);
	}
	return mx;
}

 

깊이 우선 탐색을 통해 전파할 수 있는 최단 속도를 구하기 위한 함수

 

 

문제풀이

1. 변수 n, temp에 값을 입력 받고, 1~n-1노드의 직속 상사 번호를 입력 받아 역/단방향으로 edges를 초기화한다.
2. dfs함수에 루트 노드의 번호인 0을 매개변수로 전달하여 호출한다. 함수 내부에서 변수 cn에 값을 전달받는다.
3. 기저 조건으로 cn의 인접리스트가 비어있다면 0을 리턴한다.
4. 정수형 벡터 times를 초기화 하고, 인접 리스트를 순회한다. 매 루프마다 자식 노드의 번호를 nn에 저장한다.
5. dfs함수에 nn을 매개변수로 전달하여 호출하고, 결과를 times에 추가한다.
6. sort함수를 통해 times를 내림차순으로 정렬하고, 변수 mx를 0으로 초기화한다.
7. times를 순회하며 mx와 times[i]+i+1을 비교하여 더 큰 값을 mx에 저장한다.
8. mx를 리턴한다.
9. dfs함수의 최종 결과를 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 병렬 처리가 가능하므로 서브트리의 너비/깊이를 고려해 순서를 고려하는 것을 정렬을 통해 해결하였다.
2. 가장 시간이 많이 걸리는 노드부터 우선 순회하되, 결과값의 최대값을 리턴해야한다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 50;
vector<int> edges[N];

int dfs(int cn) {
	if (edges[cn].empty()) return 0;

	vector<int> times;
	for (int nn : edges[cn]) {
		times.push_back(dfs(nn));
	}
	
	sort(times.begin(), times.end(), greater<int>());
	int mx = 0;
	for (int i = 0; i < times.size(); ++i) {
		mx = max(mx, times[i] + i + 1);
	}
	return mx;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, temp; cin >> n >> temp;
	for (int i = 1; i < n; ++i) {
		int p; cin >> p;
		edges[p].push_back(i);
	}

	cout << dfs(0);
}