[SWEA 1238] Contact C++

 

SW Expert Academy

 

 

문제풀이

 

비상연락망과 연락을 시작하는 당번에 대한 정보가 주어질 때, 가장 나중에 연락을 받게 되는 사람 중 번호가 가장 큰 사람을 구하는 문제다.

 

 

비상연락망

 

위 그림은 비상연락망을 나타낸 그림이고 각 원은 개개인을 의미하며, 원 안의 숫자는 그 사람의 번호이다.

빨간원은 연락을 시작하는 당번을 의미하고 화살표는 연락이 가능한 방향을 의미한다.

 

 

가장 나중에 연락을 받게 되는 사람을 찾기 위해서 BFS를 통해 depth 배열에 연락받는 순서를 저장해주었다.

그림을 보면서 설명을 해보겠다!

 

먼저 연락을 시작하는 당번은 1로 둔다.

 

 

 

비상연락망이 가동되면 2번은 연락가능한 7번과 15번에게 동시에 연락을 취한다.

7번과 15번의 depth는 2가 된다.

 

 

 

그 다음엔 7번이 1번에게, 15번이 5번에게 연락을 취할 것이다.

그러면 1번과 5번의 depth는 3이 된다.

 

 

그 다음 1번이 8번과 17번에게 동시에 연락하고, 이와 동시에 4번은 10번에게 연락한다.

7번과 2번의 경우는 depth가 0이 아니므로, 즉 이미 연락을 받은 상태이기 때문에 다시 연락하지 않는다.

8번, 17번, 10번의 depth는 4가 될 것이다.

 

 

 

 

더 이상 연락할 수 있는 사람이 없으므로 여기서 연락이 끝나게 된다.

이제 depth 배열에서 값이 가장 큰 인덱스들 중 제일 큰 인덱스를 찾으면 17번을 구할 수 있다. 

 

 

C++ 코드