vjerksen   3년 전

해킹할 수 있는 방향대로 방향 그래프를 만들어준 후에, BFS를 이용해서 가장 많이 해킹할 수 있는 컴퓨터를 저장했습니다. 

그리고 오름차순으로 정렬해서 출력하게 했고, Test case는 모두 맞았습니다. 다른 질문들의 Test case도 다 맞게 나오는데 

어디서 문제인지 모르겠습니다. 도와주세요 고수님들

amok   3년 전

코드가 잘 이해가 안가는데, 그냥 단순히 "BFS를 이용해서" 라고 하지 말고, BFS를 어떻게 이용했는지 좀 자세히 적어주시면 좋을 것 같습니다.

amok   3년 전

읽어보니 각 노드마다 BFS를 수행하고, BFS트리의 높이(혹은 BFS의 시작 노드로부터 최단거리가 가장 먼 노드까지의 최단거리)를 구한 후, 그 높이가 가장 높은 정점을 출력하셨네요. 다음 반례를 참조하시기 바랍니다.

7 5
2 1
3 2
5 4
6 4
7 4

일단 제시하신 방법은 틀릴 뿐더러, 느립니다. BFS를 N번 수행해야 하기 때문입니다. BFS(혹은 DFS)를 노드의 개수만큼 수행하는 다른 방법이 있으나, 이 문제를 풀기는 너무 느립니다. 문제 분류가 DFS, BFS로 되어 있는데, 이 두 기본적인 탐색 알고리즘으로는 풀 수 없는 문제입니다. 풀어보진 않았지만 Strongly Connected Component 알고리즘으로 이 문제를 풀 수 있을 것 같습니다.

vjerksen   3년 전

to. amok

친절하고 성의있는 답변 감사합니다.  

근데 왜 강결합요소를 사용해서 문제를 해결할 수 있다고 생각하시는지 알 수 있을까요?

강결합요소 내에 있는 노드들은 서로 간에 이동이 가능하다고 알고있는데 위의 반례에선 사이클이 형성되지 않습니다.

힌트 조금만 더 주시면 감사하겠습니다!

amok   3년 전

제가 제시한 반례에서는 사이클이 없기 때문에 강결합요소로 노드를 묶으나 그렇게 하지 않으나 차이가 없습니다. 오히려 강결합요소 찾기 알고리즘을 수행하는데 O(N+M)의 오버헤드가 추가로 들죠. 그러나 제가 제시한 반례가 가능한 입력의 전부가 아니므로, 입력으로 주어지는 그래프에 사이클이 있을지 없을지 알 수 없습니다. 사이클이 있는 그래프라면 하나의 강결합요소를 하나의 노드로 볼 수 있어서 탐색 시간이 줄어듭니다. 노드 1000개 정도를 하나로 볼 수 있다면 훨씬 빠르겠죠. 또한 강결합요소로 묶어줘서 사이클을 제거할 수 있습니다. 사이클이 없는 방향 그래프(DAG)는 훨씬 다루기 좋죠.

...... 라고 처음에 생각해서 강결합요소로 분해 후 풀이를 시도했으나, O(MN) 보다 빠른 풀이를 아무리 해도 생각해내지 못했습니다. DAG로 만들어봤자 소용없었습니다. 입력에 사이클이 있는 경우는 좀 줄였을지 모르나, 입력이 DAG인 경우는 전혀 줄인 것이 없는, 최악의 경우 theta(MN)인 단순한 알고리즘을 짜서 제출했습니다. 그런데 그렇게 했더니 맞았습니다.
개인적인 의견으로 이 문제 좀 이상한 것 같습니다. 정답 받은 다른 분들의 코드를 살펴봐도 다들 최악의 경우 theta(MN)입니다. M과 N이 크기가 저정도면 theta(MN)으로는 안 되는데... theta(MN) 보다 빠른 방법이 있긴 한 건가요? 아무튼 SCC로 분해해서 정답 판정을 받을 수 있는 것은 맞습니다.

vjerksen   3년 전

to. amok

답변 정말 감사합니다! 다른 분들한테 물어보니까 단순 BFS로 해결해도 time limit을 지킬 수 있다고 하더라고요.

이 기회에 강결합요소에 대해서 더 공부할 수 있었습니다. 다시 한번 감사합니다.

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