[백준]1135번 뉴스 전하기 - C/C++

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

1135번: 뉴스 전하기

문제

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작한다.

입력

첫째 줄에 직원의 수 N이 주어진다. 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어진다. 0번 직원 (오민식)은 상사가 없기 때문에 -1이고, 나머지 직원 i의 상사 번호는 i보다 작거나 같은 음이 아닌 정수이다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 소식을 전하는데 걸리는 시간의 최솟값을 출력한다.

---

 

 기본적인 원리는 자신이 전화를 해야 할 때 가장 오래 걸리는 자식에게 먼저 전화를 걸면 되는 구조이다. 이것을 하기 위해서는 자기가 얼마나 걸리는지 알아야 한다.

 

- 리프 노드의 경우 전화만 받으면 되므로 1이다.

- 일반적인 노드의 경우 자신이 걸리는 시간의 최솟값은 가장 오래 걸리는 자식들에게 먼저 전화를 주는 것인데 전화를 할 때마다 시간이 흐르므로 자신 아래로 전화를 다 거는 시간은 자식1 , 자식2 + 1 ,... 중 가장 큰 값이 된다. 반환 값은 자신한테 걸려오는 시간 1분이 있으니 1을 더한다.

 

- 이때 값은 자신에게 전화가 왔을 때 1분의 시간이 흐른 것으로 가정하므로 dfs(0)을 한다면 0이 전화를 받는 시간까지 포함이 된다. 하지만 전화는 0부터 시작하므로 그 값에서 1을 빼주면 답이 된다.

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

vector<vector<int>> arr(51);
int temp[51] = { 0 }, parent[51]={0}, child[51] = {0};
int n,a,tick=1,ans=0;

int compare(int a, int b) {
	return a > b;
}
int dfs(int idx) {
	if (!arr[idx].size()) {
		return 1;
	}
	int ret = 0;
	vector<int> v;
	for (int i = 0; i < arr[idx].size(); i++) {
		v.push_back(dfs(arr[idx][i]));
	}
	sort(v.begin(), v.end(),compare);
	for (int i = 0; i < v.size(); i++) {
		ret = max(ret, v[i] + i);
	}
	return ret + 1;
}

int main() {
	cin >> n >> a;
	
	for (int i = 1; i < n; i++) {
		cin >> parent[i];
		arr[parent[i]].push_back(i);
		child[parent[i]]++;
	}
	
	cout << dfs(0)-1;
	return 0;
}

---

    DP문제를 풀려고 DP 카테고리의 문제를 선택했는데 트리 문제가 나왔다. 왜 DP 카테고리에 있지 싶었는데 풀고 나니 트리 + DP의 문제라는 것을 알게 되었다. BFS 형식으로 풀려하다가 뭔가 이상해서 생각해보니 DFS로 푸는 것이 훨씬 논리적인 것 같았다. 그래서 풀었는데 처음에는 단순히 자식이 많은 순서로 전화를 주면 되겠다는 생각을 했지만 이내 그렇지 않다는 것을 깨달았다. 그래서 생각을 더 해보았지만 생각이 나지 않아 구글링의 힘을 조금 빌렸다. 마지막에 1을 빼는 것이 문제를 완전히 이해하고 풀었는지 결판 짓는 것 같다!

    이 문제 말고 1106번을 먼저 풀었는데 제출을 무진장했는데 다 '실패했습니다'가 떴다. 아침에 병원에 갔다가 카페에 가서 문제를 풀다가 화가 난 나머지 집에 와서 에어컨 바람을 쐬며 좀 쉬었다. 예시도 잘 나오고 예외 처리 문제 같은데 도저히 반례가 안 보인다. 내일 차분한 마음으로 보면 눈에 보일까? 아직은 난 무죄라고 생각한다..