BOJ 1939 중량제한

이 문제는 나도 모르게... 습관적으로 문제 분류를 보게 되었다.

이분 탐색 + bfs 로 푸는 문제인데, 일단은 이렇게 안 푼다고 한 번 생각해보자.

모든 경로를 다 보고 각 경로를 구성하는 간선의 가중치 중 최소의 가중치를 찾으면 그 값이 그 경로의 중량 제한인데, 중량 제한의 최대값이므로 모든 경로에서 구해낸 그 값들 중 최대값을 구해야 한다. 하지만 모든 경로를 다 가보는 것도 못 구현하겠고, 설령 한다해도 시간이 엄청 걸릴 것이다. 근데 이 문제를 이렇게 생각하다보니 얼마 전에 봤던 코드 몬스터 2번 문제와 똑같다는 느낌이 든다. 하지만 코드 몬스터 2번 문제는 입력 데이터 제한이 더 커서 단순히 이분 탐색과 bfs로 풀어서는 시간 초과이다. BOJ slack에 검색해서 고수님들이 말씀하신 걸 보니 그 문제는 maximum spanning tree와 lca를 이용해서 풀거나 maximum spanning tree와 (다익스트라 or bfs)로 풀면 된다는 것 같다. 비슷한 문제로는 이 1939 중량제한 문제와 3176 도로 네트워크 문제가 있다.

일단 이 문제를 이분 탐색과 bfs로 풀어보고, 할 수 있다면 mst를 이용해서도 풀어봐야겠다.

1. 이분 탐색과 bfs(혹은 dfs)
이분 탐색으로 중량 제한의 최대값 MAX를 정하고 bfs로 출발지에서 목적지까지의 경로를 탐색하면서 MAX 이상의 가중치를 가지는 경로로만 이동해서 목적지에 도착하는 경로가 존재하면 다시 이분 탐색으로 범위를 좀 줄여서 해보고.. 이런 식으로 중량 제한의 최대값을 찾아나갈 수 있다. 좋은 문제같다. dfs, bfs로 각각 구현해 봐야겠다.

그리고 이분 탐색을 할 때, ans라는 변수를 써서 답을 저장해도 되지만, l이나 r값만으로 답을 구할 수 있다. 이 문제에서는 이분 탐색에서 mid값이 성립이 되면, (최대값을 찾아야 하므로) l = mid+1, 성립이 안되면 r=mid-1을 한다. 잘 생각해보면 실제 정답이 되는 mid값을 찾은 후에는 그 다음부터 구하는 mid값은 성립이 안될 것이므로 계속 r=mid-1을 하게 되고, l은 계속 성립된 mid값(정답)+1 인 상태일 것이다. 그리고 while(l<=r)인 동안 돌게 되므로 결국 r이 mid+1보다 왼쪽으로 한 칸 더 간... 바로 mid값(정답) 값이 되면서 끝난다. 이 것도 여태 엄청 헷갈렸는데, 요즘 스터디에서도 많이 배우고 다양한 방면의 문제를 접하면서 깨닫게 된 것 같다.

일단 AC를 받았는데, 다른 분들의 풀이도 보고 검색도 하다 보니 꼭 이분탐색 + bfs만 있는 것은 아니었다. 그 중 나에게 영감을 준 블로그 글이 두 개 있다. : onjo0127님의 블로그, http://kthng.tistory.com/15

2. dijkstra(...bfs)
onjo0127님의 글에서 onjo0127님이 자신의 풀이가 다익스트라와 비슷하다고 말씀하시는데, 순간 왠지 위에서 말했던 코드 몬스터 2번을 풀 때, 다익스트라로 풀 수 있다는 것과 관련이 있어보인다는 생각이 들었다. 그래서 잠깐 저녁먹으러 갔다오면서 다익스트라로 어떻게 풀지 생각해 봤다.
그리고 생각해보니 정말 다익스트라로 가능하다. 다익스트라는 원래 한 점에서 나머지 각 점까지의 최단거리를 찾는 알고리즘이지만, 조금 변형해서 최장거리, 아니 어떤 점까의 최대 중량 제한을 찾는 것으로 하면 가능하다. priority_queue에 후보를 넣고, 그 중 가장 중량이 큰 후보를 뽑으면 그 점까지의 최대 중량은 확정되는 것이고, 그럼 그 점에서 또 후보들을 찾아보고, 후보의 최대 중량 값은 이전 정점의 최대 중량값과 이전 정점과 자신이 연결된 간선의 가중치(중량) 중 더 작은 값을 택하면 된다. 그리고 후보의 최대 중량 값이 더 큰 값으로 갱신될 때 큐에 넣어주면 된다. 즉, 이것도 다익스트라 처럼 출발점에서 시작해서 다른 정점까지의 최대 중량을 하나씩 확정해 나가는 것이다.
pq의 후보값중에 최대값을 뽑게 되면 나머지 어떤 정점은 그 정점보다는 값이 작거나 같다는 것이므로 어떤 정점을 거쳐가든 반드시 그 최대값보다는 작거나 같은 중량을 가질 수 밖에 없다. 이런 원리로 결정해 나가는... 다익스트라의 원리와 같다.
일단 구현해 봐야겠다. 시간은 좀 더 걸렸지만 거의 비슷하면서 AC를 받았다.

3. MST(이 문제에서는 Maximum) + dijkstra
Maximum Spanning Tree에 대해 생각해 봤는데, 일단 스패닝 트리는 그래프에서 일부 간선을 선택해 만든 트리이다. 즉 n-1개의 간선으로 n개의 정점들을 연결하고 있다. 여기서 볼 Maximum Spanning Tree 최대 스패닝 트리는 간선의 (가중치)합이 최대가 되도록 그래프에서 간선을 선택해서 만든 트리이다. 그렇다면 왜 이게 이 문제와 코드몬스터 2번문제에 유용(필요)한지 차근차근 설명하려고 한다.
각 경로의 중량 제한은 각 경로에서 가장 작은 간선의 가중치가 된다. 그렇기 때문에 직관적으로 답이되는 최대 중량 제한을 이루고 있는 경로는 분명 최대 스패닝 트리(MST) 위에 있을 것이다. 스패닝 트리로 모든 정점들이 이어져 있으므로 경로가 없지 않을까 하는 걱정은 안 해도 된다. 그리고 스패닝 트리는 n-1개의 간선으로 이루어져 있기 때문에 다익스트라를 돌릴 때, 시간복잡도가 확 줄어들게 된다.
이제야 왜 코드 몬스터 2번 문제에서 최대 스패닝 트리가 필요한지 깨달았다. 일단 이 중량 제한 문제도 최대 스패닝 트리를 이용해서 풀어봐야겠다.
AC를 받았다. 시간이 좀 더 걸린다. 하지만 코드 몬스터 2번처럼 쿼리가 많이 들어오는 경우에는 시간을 훨씬 줄일 수 있을 것이다. 이 문제는 쿼리가 하나밖에 없는 것이므로 MST로 그래프를 만드는 전처리 과정이 O(ElogE)로 시간복잡도를 대부분 차지할 것이다.

4. MST + LCA
내가 아직 LCA를 모르기 때문에 공부해 봐야한다.
드디어 알아냈다. BOJ 3176 도로 네트워크 MST를 만들면 이 문제와 푸는 방법이 똑같다.
일단 MST를 만들면 트리가 된다. LCA는 최소 공통 조상을 찾는 알고리즘인데, 여기서는 배열에 저장하는 값을 조상과 최소값까지 같이 저장해놓는데, 이렇게 하면 최소 공통 조상을 찾으면서(O(logn)) 최소값을 비교해서 그 중 최소값을 찾으면 그것이 정답이다. 왜나하면 트리에서 한 정점에서 다른 한 정점까지의 경로는 그 두 정점의 최소 공통 조상을 지나게 되고, 최소 공통 조상을 구하는 과정에서 그 경로를 다 보게 되기 때문이다.
dp배열을 전처리하는데 O(nlogn)이 걸리고, 답을 구하는데는 한 쿼리당(logn)이 걸린다.
이 문제는 쿼리가 한 개인 셈이므로 O(nlogn + logn)이 걸릴 것이다.
풀어봐야겠다. AC를 받았는데, 시간은 꽤 빠르게 나왔다. 음 시간은 서버의 영향도 좀 받기 때문에 완전 신뢰할 수는 없겠지만...

일단은 많은 공부를 하게 되었고, LCA에 대해서도 알게 되었다.
힘들게 익힌거 잊지않도록...복습을 꾸준히 하자!

이 글을 다시 보는데, 3. MST+dijkstra에서 MST를 만들었으면 트리이므로 한 점에서 다른 한 점까지의 경로는 하나밖에 없다. 그냥 간단하게 dfs를 돌려도 될 것 같다. - 13905 세부 문제를 풀면서 dfs로 해봤는데 내 부족한 실력때문인지... 좀 까다로웠다.