dohoon   3년 전

위상정렬로 풀 수 있다는 것은 알고 있습니다.

그런데 풀다보니까,

위상정렬을 위해 주어진 간선들의 방향을 정반대로 바꾸고, 하향식 DP를 진행한다면..?

결국 그 두 가지 풀이는 동치가 아닌가 라는 생각이 들었습니다.

그래서 저는 하향식 DP를 시도해보았습니다.

일단 이 문제에 대해 proof by AC를 했습니다.

제 생각을 검토해주실 고수 분들 구합니다..!

adfsfsf   2년 전

고수는 아니지만, 개인적인 의견을 적어보자면 상향식과는 달리, 하향식으로 하려면 이미 검토한 노드를 다시 검토해야 하는 문제가 생깁니다. 문제의 예시만 해도 그런 문제가 나오는데요, 4->2를 한 후, 2->1을합니다. 이후, 4->3, 3->1을 하는데, 이 과정에서 1번 건물을 2번 확인해야 합니다. 상향식에서와 달리 하향식으로 dfs나 bfs를 할 경우에는 1번 건물이 이미 visited 처리가 되어서 다시 검토되질 못합니다. 이런 문제점에 대한 해결만 가능하다면 하향식도 충분히 가능합니다. 그런데, 굳이 추가적인 문제를 만들어가면서까지 하향식을 하려는 사람은 없을 것 같네요...

adfsfsf   2년 전

하향식으로 할 경우, 아래로 내려가기 전에 상위의 노드들을 전부 검토를 해야 한다는 것을 발견했습니다. 그런데 그러려면 위상정렬을 하면 안 되는 것 같네요. 이미 아래쪽으로 정렬을 했는데, 아래로 가려면 위쪽을 확인해야 하니까요.

dohoon   2년 전

무슨 말씀인지 제대로 이해하지 못했습니다.

일단, 제가 예전에 쓴 글이고, 저는 이 방법이 먹히는 것이 맞다는 것을 확인했으니 제 논리를 좀 더 상세히 적어보겠습니다.

DAG는 모든 간선들을 뒤집어도 DAG입니다.

proof. 뒤집힌 DAG에 사이클이 있다고 가정해봅시다. 다시 원래의 DAG처럼 간선을 뒤집으면 여전히 방향만 반대인 사이클입니다. 따라서 가정에 모순입니다. QED

그러면 뒤집힌 DAG에 대해 DFS를 이용하여 정렬 리스트를 만드는 방식을 적용하면 뒤집기 전의 outdegree가 현재의 indegree임으로 위상정렬을 똑바로 수행됩니다.

따라서 아무 문제가 없지만, 정렬 리스트가 원래 알고리즘과 정반대입니다.

독특하게도 이 점은 유용합니다. 원래 이 알고리즘이 역순 정렬 리스트를 반환하기 때문에 한 번 더 뒤집힌 이 상태는 오히려 정순입니다.

따라서 간선을 뒤집고 위상정렬을 하고 나면 정렬 리스트 생성 필요없이 바로 DP를 써도 정당합니다.

이런 점에서 저는 좋다고 생각했습니다.

하지만 [문제집] 같은 문제를 풀 때 이 방법은 직관적이지 않습니다. 저도 대회에서 이와 똑같은 문제를 마주했다가 망쳐서 요즘 반성하고 있습니다.

암튼, 제 논리는 여기까지입니다.

참고로 오늘 SCC를 배웠는데 SCC에서도 간선 뒤집기가 핵심 아이디어로 사용되더군요... 신기했습니다!

adfsfsf   2년 전

중요한 사실이 있는데요, 이 문제에는 사이클이 없어요. 사이클이 생기면 시작점이 생길 수가 없고, 따라서 모든 건물이 건설 가능하다는 조건에 위배됩니다.

adfsfsf   2년 전

만약 사이클이 있는 문제였다면, 적어주신 게 맞습니다. 하지만 사이클이 없는 문제이기에 방향이 바뀌면 풀이가 불가능해진다고 봐야 합니다.

문제에 사이클이 있다고 하셨으니 어떤 사이클 a->b->c->a 순서가 존재한다고 가정하겠습니다. 해당 사이클에서는 a를 지으려면 c가 필요합니다. 그리고 c를 지으려면 b가 필요하고, b는 a가 필요하죠. 어떤 사이클이라도 이러한 3노드로 간단히 일반화가 가능합니다. 하지만 어떤 사이클에서도 이 중 한 건물이라도 지을 수 없다는 것이 증명되었습니다.

사이클이 없기에 역정렬을 하면 그건 그냥 역순이고, 따라서 정방향 정보를 함께 가져야 풀 수 있습니다. 비효율적이 되는 이유입니다.

bconfiden2   2년 전

질문자분께서는 사이클이 있다고 말씀하신게 아니라, DAG 을 뒤집더라도 싸이클이 존재하지 않음을 증명하신 것 같습니다!

저 역시 위상 정렬 알고리즘을 모르는 상태(DAG은 알고있었습니다)로 이 문제를 접하게 되었고, 질문자분과 비슷하게 그래프를 반대로 뒤집은 뒤 DFS 를 통해 DP배열을 업데이트하면서 풀었습니다.

답변자분께서는 노드의 중복 탐색을 걱정해주셨는데, 예시로 들어주신것처럼 4 - 2 - 1 에서 1번 노드가 방문되었기에 1번의 건설값을 dp에 저장한 뒤, 4 - 3 - 1 에서 방문할 때는 1번 노드의 dp 값을 활용할 수 있다고 생각합니다.

정방향에서 indegree 가 2 이상인 노드(다른 여러노드들의 건설이 완료되어야 실행가능한 노드)는, 역방향으로 뒤집을 때 outdegree 가 높아지는데, 이러한 노드들의 dp값에 대해서는, dfs 에서 out으로 연결된 노드들을 탐색하는 과정에서 그들 중 최대값을 취하면 된다고 생각했습니다!

아래는 예제 입력 2번의 그래프인데,

4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2
4

dfs가 4번노드부터 시작한다고 하겠습니다.

먼저 4 - 1 을 탐색하여, 1번노드에는 연결된 정점(역방향)이 없으므로 dp값이 결정됩니다.

다음으로 4 - 2 로 들어가는데, 2번 노드에서 다시 1번 노드를 탐색해야하지만, 방문한 정점이므로 dfs를 호출하지 않고 결정되었던 dp값을 활용합니다. 2번노드에는 다른 연결된 정점들이 없기 때문에 2번노드의 dp값도 결정됩니다.

4 - 3 으로 들어갈 경우, 3번 노드는 1번과 2번노드를 방문해야하지만, 둘 다 앞서서 방문했기 때문에 dfs를 호출하지 않고 dp값을 사용합니다. 이 때 두 dp 값들 중 큰 값을 취해서 3번노드의 dp값을 결정합니다.

제 코드는 https://www.acmicpc.net/source... 인데, 질문자님과 답변자님은 어떻게 생각하시는지 궁금합니다.

dohoon   2년 전

같은 생각이신 것 같습니다.

쓴지 오래됐고, 현재는 생각이 정리되었는데 혼란을 주는 것은 아닌가 싶네요..

이런 형태의 단순한 위상정렬+DP 문제에서만 쓸 수 있는 사소한 테크닉 정도로 생각하고 넘어가려 합니다...

bconfiden2   2년 전

아하 알겠습니다 감사합니다!

저는 오늘 따끈따끈하게 풀어본 문제라... 위에서 링크하신 문제집 문제를 풀면서 더 익혀가보겠습니다!

adfsfsf   2년 전

@bconfiden2 님께서 적으신 방향이 정방향입니다. 문제를 해결하기 위해서 정렬해야 하는 방향은 무조건 최종 건물이 첫 건물인 방향입니다. 반대 방향으로는 갈 수가 없고요. 왜냐하면 시작 건물이 여러 개가 되면 출발점이 늘어나는 셈이니까요.

즉, 제가 생각한 역방향은 최종 건물이 dfs에서 가장 깊이가 큰 노드가 되는 방향인 겁니다.

adfsfsf   2년 전

문제에서 주어지는 방향이 정방향이라고 생각하면 적으신 게 맞습니다. 아니, 오히려 역방항으로 풀어야 하는 문제인 거죠. 정방향쪽이 손해고요. 저는 문제를 풀기 위해 정렬해야 하는 방향을 정방향이라 생각했던 겁니다.

사이클은 이 문제에 존재하지 않고, 따라서 정방향과 역방향은 완전히 다르며, 둘 중 한 방향만이 문제를 효율적으로 풀 수 있는 방향입니다. 저는 정방향이라 하면 올바른 방향이란 이미지가 커서 위와 같이 생각했던 것이고요.

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