ckdgus2482   2달 전

메모이제이션하기 까다로운 문제인것 같아 조합탐색에서 가지치기를 하려고합니다.

일단 N이 1만이니 그래프표현은 인접행렬으로는 안될것이라 생각해서 리스트 방식으로 구현했습니다.

처음 시도는 단순하게 구현을 하려고 탐색은 DFS로 하고 도로는 vector<vector<pair<int, int>>>로 표현했습니다.

아이템이 pair인 이유는 연결된 지점하고 도로의 무게제한을 같이 저장하기 위한 것입니다.

시간초과가 났습니다.

두번째 시도에서는 도로 표현을 달리 해보았습니다.

아무래도 가지치기 효율이 좋으려면 적당히 좋은 해를 최대한 빨리 찾아야하므로 연결된 지점의 리스트를 저장할때 도로 무게제한이 큰것부터 탐색될 수 있도록 vector<multimap<int, int, greater<>>>을 써서 무게제한이 큰 순으로 정렬되도록 하였습니다. insert과정에서 오버헤드가 좀 있겠지만 O(lgM)이니까 허용가능한 오버헤드라고 생각했고 약간의 오버헤드를 감수하더라도 가지치기 효율을 높이는게 더 중요하다고 생각했습니다.

그러나 여전히 시간초과가 났습니다.

세번재 시도는 휴리스틱 알고리즘을 도입하였습니다.

본격적으로 탐색을 하기 전에, BFS로 최단경로를 찾아서 그 경로의 무게제한을 해로서 세팅해놓았습니다.

하지만 시간초과는 여전합니다. 휴리스틱 알고리즘이 있으니 정렬을 미리 안해놔도 되지 않을까 싶어서 다시 첫번째 시도처럼 도로를 벡터로 바꾸고도 돌려봤지만 그래도 안되네요.

이제 제가 생각했을때 해볼만한 시도로 남은건 src->dst랑 dst->src를 같이 탐색시켜보는건데, 이건 구현이 워낙 귀찮아서 일단 보류중입니다.

괜찮은 최적화 방법이 있으면 소개좀 해주시기 바랍니다.

amugeona   2달 전

bool BFS(s, e, v) : s에서 e로 무게 v의 차량이 이동할 수 있는지의 여부

로 정의하면 v가 일정 수준으로 커지면 BFS는 false가 날 것이고, 그 전에는 true가 날 것입니다.

이런 생각으로 접근하시면 됩니다.

ckdgus2482   2달 전

v를 1씩 증가시키면서 BFS를 계속 돌리라는 말인가요?

그러면 답이 K라고 하면 K번 BFS를 수행하는데 너무 느린거 아닌가요?

시간복잡도가 O(K(|V|+|E|)), 1<=K<=100000000 이 될텐데요.

amugeona   2달 전

이분 탐색의 아이디어는 저 사실에 대한 관찰로부터 시작됩니다. :)

BFS( s, e, low ) = true 이고, BFS( s, e, high ) = false 를 만족하는 low와 high가 있을 때, 

mid = (low + high) / 2

로 정의되는 미드가 있다고 합시다.

BFS( s, e, mid ) = true 일 경우, low ~ mid 사이의 값들은 모두 BFS의 결과가 true일 것이므로 검사할 이유가 없습니다.

반대로 BFS( s, e, mid ) = false 일 경우, mid ~ high 사이의 값들은 모두 BFS의 결과가 false일 것이므로 역시 검사할 이유가 없습니다.

따라서 모든 범위 K에 대해서 검사를 하지 않고도 문제를 해결할 수 있습니다.

더 궁금하신 것이 있으시면 아래 댓글 달아주세요.

ckdgus2482   2달 전

조언해주신대로 해서 해결 했습니다. 감사합니다.

메모이제이션 적용할 아이디어도 떠올라서 DP로도 한번 풀어봐야겠네요.

댓글을 작성하려면 로그인해야 합니다.