[BOJ 25398, 고민중] 트리와 집합과 쿼리

개인적인 난이도

안풀어도되는데굳이고민중

 

안풀어도되고 난이도도 어렵고
백준 골드따리가 건들필요도 없고
풀어도 도움 안 될 거 같은 문제인데

수학 대학원에서 그래프를 공부중인 (ps는 해본적 없는)친구가 갑자기 문제랑 아이디어를 주길래 고민중이다
이런 문제는 친구네 업계에선 안 어려운 문제라고 함

아이디어가 어려운 문제라면 구현은 쉽지 않을까? 라고 생각해서 도전해보려고 한다

그냥 해본 추측

1. 쿼리가 엮였으니까 세그먼트 트리를 쓰지 않을까
2. 시간내에 안되면 어려운 최적화가 필요하지 않을까
3. 백트래킹으론 안풀리는 문제인가

 

예제(빨간돌을 파랑으로 옮기기)

친구 말 요약

1. 트리 위에서 A에서 B로 순차적으로 돌을 옮기는 게 가능한지를 묻고 있음
2. 아무거나 루트를 하나 잡고 리프를 레벨 0이라고 하면
3. A에서 가장 레벨이 낮은 B의 점으로 갈 수 있는지를 체크하면 된다
4. 레코드를 모든 방식에 대해서 만들어야 하는지는 나도 모르겠다
5. 이런 문제를 Graph reconfiguration이라고 함
6. 그래프가 V,E로 주어져있으면, A와 B는 V의 부분집합으로 주어진 정보이고, 이 문제에선 V가 주어졌다
7. 루트는 그냥 아무거나 잡고 해라
8. 아니면, A랑 B가 있을때 A에서 B와 가장 가까운 점을 잡고 B에서 가장 깊은 점으로 가는걸 테스트해라
9. NP hard나 그보다 어려울것이다
10.  

 

이걸 풀 수 있을지는 모르겠으나 세그먼트 트리 공부 후 트리와 쿼리를 처리하는 문제를 좀 풀어본 뒤 시도해보겠다