[백준] No.25760 - 귀경길 교통상황을 알려드립니다 (C++)

문제

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

25760번: 귀경길 교통상황을 알려드립니다

 

 

풀이

 

solved.ac 난이도: Gold 2

 

 

생각해본 풀이의 예외 케이스를 도저히 찾지 못해서 다른 분의 풀이를 참고해서 해결하였다.

 

 

틀린 풀이

일단 내가 생각해 본 풀이는 그리디 방식이다.

N개의 노드에 N-1개의 간선이 있다면, 루프가 생길 수 없기 때문에 트리 형태가 된다.

1번 노드가 탈출구 이기 때문에 1번 노드를 루트로 선택하면 트리가 형성된다.

간선은 양방향이지만, 항상 1번 노드에서 차량이 빠져나가기 때문에 모든 차량은 후진할 필요는 전혀 없다.

 

이때 교통체증이 발생하는 경우는  트리의 같은 level(depth)에 2대 이상의 차량이 있을 때이다. 

 

다음과 같은 서브 트리를 생각해 보자.

k개의 하위 노드(모두 같은 level)에 모두 차량이 있을 때, 이 차량들이 해당 서브 트리의 루트까지 모두 빠져나가기 위해서는  k+1분이 걸린다.

 

가장 마지막으로 통과한 차량(붉은 별표)은 결국 k-1분 동안 대기하다가, 2분만 움직여서 통과하게 된다.

k-1(대기시간= level에 존재하는 차량 개수 -1) + 2(루트를 통과하는 데 걸리는 시간= level)

 

다른 서브 트리에 존재하더라도 결국 1번으로 올라가면,  1번(root)을 통과할 때 같은 level인 차량끼리는 서로의 통행을 방해하게 된다.

 

모든 차량의 이동을 시뮬레이션하지 않더라도 가장 마지막에 탈출하는 차량의 시간이 정답이기 때문에, 마지막 차량만 생각해 주자.

항상 가장 level이 높은(깊이가 깊은) 곳의 차량이 마지막에 빠져나간다는 약속을 하면 정답은 다음과 같다.

 

(대기시간) + (마지막 차량이 루트를 통과하는 데 걸리는 시간)

= (대기시간) + (마지막 차량의 level)

 

여기서 대기 시간은 2개 이상의 차량이 존재하는 level에 대해서 발생하는 대기 시간을 모두 더해주어 구하였다.

하지만 이런 풀이는 생각해 본 케이스에서는 모두 맞지만, 정답을 맞히지는 못 하였다.

 

 

 

따라서 다른 분이 해결한 풀이로 다시 풀어보았다.

 

https://newdeal123.tistory.com/95

서울과학기술대 알고리즘 경진대회 참가 후기, 풀이

 

 

정답 풀이

 

이동이 겹칠 때, 더 깊은 level의 차량이 양보를 한다고 통과한다는 약속을 하자.

탈출한 차량을 순서대로 세우면, 늦게 통과할수록 차량이 높은 level을 가진다.

이제 시간을 돌려서 탈출한 차량들이 하나씩 원래 자신의 위치로 이동한다고 생각해 보자.

 

트리에 반대로 하나하나 차량을 투입시키면 절대로 교통체증이 발생하진 않지만, 자신이 투입될 때까지 차량이 기다려야 한다.

따라서 frontCarNum(자신의 앞차량 수) 만큼 기다리다가, 자신의 원래 위치로는 k(level)분만큼 걸려서 이동한다.

 

결과적으로 모든 차량에 대해서 가장 높은 frontCarNum + level이 정답이다.

 

 

별표가 차량 원래 위치

 

모든 차량이 level 3에 위치하고 있으므로 이 차량들이 빠져나온 순서는 다음과 같다.

 

탈출시 원래 level과 앞 차량 개수

가장 마지막에 투입되는 차량이  3(frontCarNum) + 3(level) = 6으로 가장 높은로, 6이 정답이다.

 

 

 

 

코드