[백준 / BOJ] 1135 뉴스 전하기

문제

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

1135번: 뉴스 전하기

민식이는 회사의 매니저이다. 민식이는 회사의 뉴스를 모든 직원들에게 전하려고한다.

회사의 모든 직원들은 정확히 한명의 선임이 있으며, 자신은 자신의 선임이 아니다.

모든 직원들은 모두 민식이의 간접,직접적인 부하이다.

 

모든 사람은 자신의 직속부하에게만 뉴스를 전달할수있고, 이때, 1분의 시간이 걸린다.

모든 직원이 뉴스를 전달받는 최소시간을 구하는 문제다.

 

풀이

그리디로 풀은 문제다.

 

직원 A와 A의 직속후임 B,C,D가 있으며,

직원 B의 직속후임 E,F

직원 C의 직속후임 G 가 있다고하자.

 

구조는 다음과 같을것이다.

 

A = {B,C,D}

        B = {E,F}

        C = {G}

        D = {}

                E = {}

                F = {}

               G = {}

 

이때, 최소경로는

(직원 A가 직원 B에게 뉴스를 전파하는 과정을 A->B라 표현하자)

 

1. A->B (1분)

 

2. A->C, B->E (2분)

 

3. A->D, B->F, C->G (3분)

 

으로 3분의 시간으로 모든 직원에게 뉴스를 전파할수있다. 

위 경로를 보면, 뉴스를 우선적으로 전파할 직원을 선택할때,

 

자신과 동시에 전파할수있는 직원중 더 오랜시간동안(많이) 전파해야하는 직원을 우선적으로 선택하는것을 알수있다.

(더 많이 전파해야하는 직원을 항상 우선적으로 선택하면 자신과 동시에 전화할수있는 시간이 늘어남으로 항상 이득임을 알수있다.)

 

위 로직을 그대로 구현했다.

 

바텀업으로 구현했다.

 

이때, 자신의 부하들이 각각 전파해야할 직원의 수를 체크하며 더 오랜시간 전파해야하는 직원부터 전화를 걸며 올려줬다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1135%20%EB%89%B4%EC%8A%A4%20%EC%A0%84%ED%95%98%EA%B8%B0/main.cpp

devxb/JJUNalgo