[내공만목] BOJ 트리와 쿼리 시리즈를 풀고 싶었다.(WIP)

트리와 쿼리 문제집을 풀면서 정리를 한 글입니다.

계속 업데이트 중.. 

(~2020-10-28)

 

 

트리와 쿼리 문제집이다.

www.acmicpc.net/workbook/view/915

문제집: 트리와 쿼리 (baekjoon)

 

보는데, 다이아 루비까지는 아니어도 플레까지의 문제라도 다 풀고 싶었다.

일단 트리와 쿼리 시리즈를 풀고는 싶지만, 전혀 트리와 친한 사람이 아니라서

검색부터 시작했다..

 

koosaga.com/135

트리와 쿼리 연습

그러던 중, 갓사과님의 글을 찾았다.

먼저 트리와 쿼리2부터 푸신 듯했다.

 

트리와 쿼리2를 풀기 위해서는 Sparse Tree를 알아야한다고 하셨다..

(근데, 난 그걸 모르지 하하하하)

 

또 다시 찾아봤다. 

namnamseo.tistory.com/entry/Sparse-Table

Sparse Table

이번엔 남남서 님의 블로그의 글을 찾았다.

굉장히 굉장히 설명이 잘 되어있었다. 한번 쭉 읽어보면, 좋은 예시와 설명이라서 바로 이해가 된다.

 

근데, u에서 K번 가면 나오는 v 라는 지점이 무엇이지는 알 수 있어도, 

u에서 v까지 몇번을 가야 하는지와 u에서 v까지의 총 비용은 어떻게 아는거지? 라는 생각이 들었다.

 

그래서 다시 갓사과님의 글을 다시 보았다.

Sparse table로 level ancestor를 빠르게 구할 줄 안다면, 간단한 케이스 분석으로 풀 수 있다.

아, 방금 알게 된 Sparse table로 LCA를 구현해야 하는구나..

 

난 근데, LCA에 굉장히 약하지.. 나 할 줄 아는게 뭐지?

 

www.secmem.org/blog/2019/03/27/fast-LCA-with-sparsetable/

O(1) LCA Algorithm (with Sparse Table)

또 찾아봤다...

음.. 그래... 근데 아니이이이이이 이게 뭐가 상관이 있는 거야야야야야야

 

후, 화가 났지만 다시 찾아보고 결국, 문제에 해당하는 풀이를 찾아봤다.

jason9319.tistory.com/317

BOJ)13511 트리와 쿼리2

음.. 일단, 글을 읽다보니 트리와 쿼리2 문제가 쿼리 2개로 나뉘어있는데, 첫번째 쿼리는

www.acmicpc.net/problem/1761

1761번: 정점들의 거리

이 문제와 같다는 것을 알게 되었다. 그래서 먼저 이것부터 풀어보게 되었다..

 

github.com/shinkeonkim/Today_PS/blob/master/BOJ/01000~01999/1700~1799/1761.cpp

shinkeonkim/Today_PS

위의 링크에서 해당 문제 풀이코드를 볼 수 있다.  jason9319님의 블로그 트리와 쿼리2 문제 풀이 코드와 거의 유사하지만, 남남서 님의 블로그 글에서 나왔듯이 2^k번째의 parent를 구하고 저장하는 DP 배열을 사용하는 방법을 바꾸어서 작성하였다. (k를 앞에 놔두라고 강조하셔서 그게 기억이 났다 이말이다!!!)

 

추가적으로, 이 문제도 풀 수 있었다.(LCA를 구하고 있으니까..)

www.acmicpc.net/problem/11438

11438번: LCA 2

아무튼 이렇게 문제를 풀면서 자연스럽게 트리와 쿼리2 문제에서 1번째 쿼리는 해결되었지만,

아직 2번째 쿼리를 어떻게 해야할지 정확히 감이 안 왔다.

 

그래서 먼저 트리와 쿼리 시리즈에 있는 문제 중에 이제 쉽게(?!) 풀 수 있는 문제부터 풀어보려 했다.

 

www.acmicpc.net/problem/3176 

3176번: 도로 네트워크

이 문제는 Sparse Table을 초기화하고, LCA를 구하는 과정에서 현재 가는 경로 상의 최소값, 최대값들을 저장하고 구하면 된다. 아무튼 코드는 아래 링크에 있으며, 위에서 살펴보았던 남남서님의 블로그 글을 "잘" 읽어봤다면 이미 이해하고 있을 IDEA이다.

github.com/shinkeonkim/Today_PS/blob/master/BOJ/03000~03999/3100~3199/3176.cpp

 

이제 진짜진짜 다시, 트리와 쿼리2로 돌아와보자.

이미 앞서서 첫번째 쿼리를 해결하는 방법은 알았다. jason9319 님의 블로그 글을 다시 보자. 

어쨌든 간에 트리에서 u -> v 경로는 u -> lca(u, v) -> v 경로로 나타낼 수 있고, u -> lca(u, v) 경로에 존재하는 노드 개수를 d1, lca(u, v) -> v 에 존재하는 노드 개수를 d2라 해보자.

 

그럼 먼저, d1이 문제에서 주어지는 k보다 크다면,  u -> lca(u, v) 경로 사이에 원하는 노드가 있는 것이고, 반대라면 lca(u,v) -> v 경로 사이에 원하는 노드가 있는것이다.

 

오.. 거의 다 온 것 같다. 이제, 갓사과 님이 말한 케이스 분석이 이건 것 같다. 코드로 구현해보자.

github.com/shinkeonkim/Today_PS/blob/master/BOJ/13000~13999/13500~13599/13511.cpp

위 링크의 코드가 해당 풀이를 적용한 풀이고, 

트리와 쿼리를 드디어 맞았다 흐엉엉

맞았다!

 

이제, 다시 갓사과님의 글로 돌아가보자.그 다음으로 푸신 건, 트리와 쿼리 1번과 3번인듯 하다.(solved.ac 난이도 순서로도 이게 맞다...(다른 건 다 다이아, 루비임...) 

 

일단, 트리와 쿼리 1을 풀어보자..

www.acmicpc.net/problem/13510

13510번: 트리와 쿼리 1

이 문제를 풀기 위해서는 Heavy Light Decomposition 라는 개념이 필요하다 한다..  하..이건 또 뭘까... 또 한번 찾아보자.

justicehui.github.io/hard-algorithm/2020/01/24/hld/

Heavy Light Decomposition

이번엔 justicehui님의 블로그 글이다.. 이전 버전의 글도 있는데 이 글이 코드가 더 좋다고 하니 이 글을 쭉 읽어보겠다.. 한번 이 글과 트리와 쿼리1 문제를 엮어서 생각해보자.

 

먼저, 트리와 쿼리1 문제를 살펴보면 두 종류의 쿼리를 처리해야 하는데, 다음과 같다.

1. u -> v로 가는 i 번째 간선의 cost를 바꾸는 쿼리

2. u -> v로 가는 경로에서 가장 큰 cost를 찾는 쿼리

 

만약, 이런 쿼리 방식이 array에서 있었다면 세그먼트 트리나 sqrt decomposition 등의 방식으로 해결가능했을 것이다. 하지만 이는 선형적이지 않은 비선형 구조에서의 쿼리이니, 생각할 수 없다. 

 

그렇다면 무엇을 써야한다? 바로, HLD(Heavy Light Decomposition)을 써야한다. 대충 이런 상황이다.

HLD가 뭐냐고 한다면, 위의 링크의 설명을 읽으면 될 것 같다.

그럼, 어떻게 구현하면되냐? 이것도 위의 링크의 설명을 읽으면 될 것 같다. (아직 설명할 정도로 능숙하게 다루는 게 아니라 공부 중인것이니까..)

 

이제, 한번 구현을 해보자. 

 

(~2020-10-28. 21: 48)