[백준] 22197. Railway

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

문제설명

• 트리가 주어지고
• 각각의 그룹이 주어지는데(문제에서 장관으로 표현)
• 그룹의 원소들은 서로 연결되어야함 ==> 그룹마다 필요한 간선이 있을 것임
• 간선마다 필요로 하는 그룹의 개수가 있을텐데, 그 개수가 일정 숫자 이상인 것들을 구하는 문제

접근법 - 실패 사례

• ETT를 이용해서 범위를 구하고 lca를 이용했으나 허점이 있었음
• 각각의 간선에 대해 그룹별로 필요한지를 확인하는 방식으로 하려고 했으나 시간복잡도 해결이 안됨
• mst를 이용하는 방법도 안되고...

접근법 - 핵심 알고리즘

• lca
• set, set의 merge(작은 것 -> 큰 것, 나중에 링크를..)
• dfs

접근법 - 아이디어

• 그룹의 원소로 최소의 서브 트리를 구성해봄
  • 최상위(root) = 원소들의 lca
  • 서브트리의 바깥(상위) 간선은 사용하지 않음
  • 서브트리의 내부에서 사용하는 간선 = root에서 원소들까지 연결하는 간선
• 그룹이 사용하는 간선을 효율적으로 파악하기
  • 간선 = 노드 = 부모로부터 노드로 들어오는 간선
  • 그룹의 lca가 되는 노드에는 "나간다"는 표시 = lca 노드 상위 간선들부터는 그 그룹을 고려하지 않는다는 의미
  • 사용되는 노드에는 그룹의 집합을 구성
  • dfs탐색 후 올라오는 과정에서
    • 자식 노드들의 set을 merge
    • 해당 노드에서 "나가는" 그룹을 처리
    • 그리고 남는 그룹 = 해당 간선이 필요한 그룹들 = 그룹 개수 파악 가능
  • 해당 간선이 정답인 경우 해당 노드를 체크 표시
• 출력
  • 간선을 훑으면서 하위노드가 누구인지 파악(간선을 그렇게 정의해서 사용했음)
  • 하위노드가 체크되어있으면 출력

접근법 - 구현

• set
  • cpp의 set을 목적에 맞게 사용하는 법을 몰라서 비슷하게 구현
  • map, count, vector
• mapping
  • 노드가 가지고 있는 set이 필요시 서로 교환이 되어야해서
  • set따로, 이들을 가리키는 인덱스따로 구현
  • reference를 응용하면 더 편할듯
• merge
  • set크기를 비교해서 작은 것 -> 큰 것으로 merge되도록 처리
  • 관련 이론 정리한 링크가 있던데 나중에 추가하겠음

후기

• 어려웠고 낯선 유형이었음