백준 12024번, 사각형 찾기 풀이
문제 백준 12024번 풀이 DFS로 짜면 TLE가 나니 다른 방법을 고려해야 합니다. $ i $, $ j $가 정해져있고, $ k_{1} $과 $ k_{2} $가 $ i $와 $ j $를 제외한 서로 다른 임의의 정점이라고 두겠습니다. $ i \to k_{1} $, $ k_{1} \to j $ 로 가는 방법이 있다고 하면 $ i $에서 $ j $로 가는 경로가 있다는 말과 같습니다. 반대로, $ j \to i $로 가는 간선도 있어야 합니다. $ j \to k_{2} $, $ k_{2} \to i $ 를 통해서 가는 방법이 있다면, 이 역시 $ j $에서 $ i $로 가는 경로가 있다는 말과 같습니다. $ i \to j \to i $로 가는 과정이 한가지 경우의 수가 됩니다. 또한, 문제에서 양방향(무..
2020.10.06