티스토리 뷰
이번에도 저번과 같이 1시간 동안 문제를 보고 풀 순서를 결정했다. 1시간 동안 문제를 본 결과, 저번에 풀었던 셋보다 더 쉽다는 것을 알 수 있었고, 내가 생각하던 난이도 순서인 3번->2번->1번 순서로 풀기로 결정했다.
3번은 크기 5만인 방향 그래프에서 a와 b의 최단 경로를 만 번 구하는 문제인데, a에서 b로 가는 간선은 ⌊b/K⌋ = 1 + ⌊a/K⌋를 만족한다(K<=5). 이 문제를 보자마자 이 문제는 스파스 테이블로 풀 수 있다는 생각이 들었다, 정점을 (N/K)+1개의 그룹들로 묶은 뒤, i번째 그룹의 j번째 원소에서 i+1번째 그룹의 k번째 원소로 가는 경로를 dp[0][i][j][k]라 하고, 이를 빠르게 구하기 위해 스파스 테이블을 사용했다. 두 테이블을 합칠 때는 첫 번째 부분의 dp를 dp1이라 하고, 두 번째 부분의 dp를 dp2라 할 때, dp[i][j]=dp1[i][k]+dp2[k][j]의 최솟값임을 활용했다. 이를 이용하면 전처리 (NlogNK3), 쿼리 한 번당(K3logN) 시간에 풀 수 있다. 구현에 특이사항이나 어려운 점은 없었고, 금방 구현해서 AC를 맞을 수 있었다.
2번은 트리에 m개의 정정 집합이 있고, 정정 집합들을 모두 연결시키도록 하는 최소 크기의 트리를 만들 때 m개의 집합 중 최소 k개에 들어가는 간선들을 구하는 문제이다. 이 문제에서는 여러 가지 접근을 시도해 봤는데, 성공한 접근의 핵심 아이디어는 어떤 정정 집합에서 나오는 트리에 포함되는 간선의 자식의 서브트리에는 집합에 있는 노드가 하나는 포함되어 있어야 하지만, 전부 다 포함될 수는 없고, 이를 만족하면 무조건 트리에 포함된다는 것이다. 정점 집합 전체에 대한 lca를 구한 뒤, 간선이 어떤 정점 집합 트리에 포함되어야 하는 시점과 빠져야 하는 시점을 이를 통해 구하고, 이를 이용해서 dfs를 돌리며 간선이 어떤 정점 집합들에 포함되는지를 관리해주면 된다. 단순히 부모와 자식을 합쳐준 뒤 포함되어야 하는 시점과 빠져야 하는 시점을 사용하면 제곱 시간 복잡도가 나오지만, small to large를 사용하면 로그 시간에 할 수 있다. 정점 집합을 넣는 데는 unordered_set을 사용했는데, 다행히도 상수가 문제되지는 않았다.
1번은 가장 아이디어가 특이했던 문제이다. 그래프 안에서 가장 큰 완전 그래프의 크기를 찾는 문제인데, 답은 K(K<=10) 이하임이 보장되고, 어떤 정점 그룹을 골라도 그룹에 있는 다른 정점으로 가는 간선이 최대 K-1개인 정점이 있다는 것이 보장된다. 뒤에 있는 특이한 조건을 사용하기 위해, 가장 degree가 작은 정점을 먼저 본다. 이 정점에서 나가는 간선은 최대 K-1개이고, 이 정점이 포함되는 완전 그래프가 있다면 최대 K-1개의 간선들로 이어지는 정점만 보면 된다. 이를 완전 탐색해 준 뒤, 이 정점을 지우고 degree를 업데이트해 준 후 반복하면 된다. degree는 priority queue를 사용해서 관리했고, 완전 탐색에는 인접 행렬 비트셋을 사용했다.
여러 가지 접근을 통해 아이디어를 빠르게 생각해낸 결과, 2시간 반 만에 플레2~다이아5 3개를 풀 수 있었다. 앞으로도 문제들을 지금 어떻게 접근했는지 기억하면서 좋은 속도를 유지할 수 있도록 하겠다.