브루트 포스에 대한 생각이 바뀌었다.

현재 진행 중인 과제이자 논문에서 두개의 Grpah가 Isomorphic한지, Isomorphic하다면 각각의 Node가 어떻게 대응되는지를 찾아야 하는 문제를 풀어야 했다.

Graph Isomorphism은 NP-Hard이자, GI-Complete한 문제로, 일반해나 다항시간 내의 해결 방법이 없는 것이 특징이다.

그리고 일반적으로 완전 탐색으로 푼다고 하면 당연하게도 $O(n) = n!$ 이기 때문에 완전 탐색은 시도 조차 안해보고.... 온갖 잔대가리를 열심히 굴려서 Graph Match Library에 Topological Sort와 Early-Stopping을 죄다 때려박은 기괴한 알고리즘을 만들었다.

거의 300줄 정도 짠거같은데...ㅠㅠ 이렇게 짜도 Graph의 Label까지 Isomorphic한지가 풀리지 않아서 멘탈이 터지고~ 교통 사고까지 나서 멘탈이 거의 승천할 뻔 했다

그러다 우연히 수학 사이트 스레드에서

Node에 Label이 있다면 준다항시간으로 풀수 있어~ 라는 글을 보았고,

* 잘 이해는 못했지만 그렇다고 브루트 포스를 썼을때 준다항이라는 것은 아니었다.

갑자기 번쩍! Label이 정해져 있으니 그것을 바탕으로 완전 탐색 하면 경우의 수가 적지 않을까? 라는 생각을 했고 실제로 계산해보니 진짜 몇개 안나오더라 ㅠㅠ

브루트포스로 짜니까 300줄이던 코드도 40줄 정도로 줄어들고,,, 속도는 더 빠르고,,, 해도 정확하게 구해지고,,,

알고리즘 수업을 들으면 마치 브루트포스를 악마 취급하는데 브루트포스도 잘 쓰면 무조건 최적해를 구할 수 있는 소중한 알고리즘 이라는 것을 깨달았다