amugeona   1년 전

요즘 헝가리안 메소드에 흥미가 생겨서 보고 있는데, 0을 커버하는 라인의 수를 최소로 하도록 하는 방법에 대해 고민에 빠졌습니다.

0 1 0 3
2 0 0 1
0 3 3 2
0 1 2 1

이 있을 때 F 모양으로 3개의 라인을 그어 0을 모두 커버할 수 있는건 직관적으로 알 수 있으나, N이 커짐에 따라 직관적으로 아는건 불가능해지겠지요...?

현재 제가 아는 방법은 이 부분을 이분매칭으로 해결하는 방법입니다. 이 때의 시간복잡도는 O(N^3)이겠네요.

0을 커버하는 라인의 수와, 라인의 정보를 구해주는 함수를 편의상 Find_Zero_Line()이라 하겠습니다.

그런데 헝가리안 메소드의 방법 자체가 O(N^3) 이라고 하는데(여기서 멘붕...) 저는 Find_Zero_Line() 이 최악의 경우 N번 호출되기 때문에 O(N^4)이 되게 됩니다.

Find_Zero_Line() 함수가 더 효율적으로 돌아갈 수 있는 방법이 있을까요? 헝가리안 메소드에 대해 크게 모르셔도, 이런 류의 문제를 경험하신 분이 있으시고, 이분 매칭 외의 방법을 고민해보신적 있으신 분은 답변 부탁드리겠습니다. (_ _)

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