BOJ 20427 - 아침은 고구마야 (Hard)
DFS를 여러번 돌리며 모든 싸이클에 대해 여러가지를 기록해둔다.
- 어떤 정점이 부모랑 이어지는지?
- 어떤 정점들이 속해있는지?
- 이 싸이클에 달린 leaf로 가는 가는 뿌리들을 잘랐을 때 최소컷
- 루트로부터 모든 정점에 대해 굳은 뿌리 혹은 가는 뿌리를 잘랐을 때 최소컷 (싸이클을 만나면 더 진행하지 않고 위에서 구한 값을 사용)
Normal 문제 기준으로 생각해보면,
덩이뿌리는 잘릴 일이 없으므로 항상 어떤 싸이클이 포함이 될 수 있냐만 검사해주면 된다.
검사해주는 과정은 루트부터 DFS를 순회하며 어떤 정점의 서브트리에 대한 최소컷이 부모로부터 그 정점으로 가는 간선의 가중치 이하라면 계속 진행해주다가 싸이클을 만나면 그 싸이클은 포함될 수 있다고 판단해주는 것이다.
Hard 문제를 풀기위해선 각 싸이클을 잘라내는게 싸이클에 달린 가는 뿌리들을 잘랐을 때의 최소컷보다 더 작아질 수 있는지를 판별해야 한다.
이건 어떤 싸이클에 대해 최소값 구간합 배열을 부모로가는 정점을 시작점으로 보고 좌우로 두 번 열심히 돌려서 판단해줄 수 있다.
따라서 시간복잡도 $O(N+M)$에 풀 수 있다.
Comments