Shortest Path Visiting All Nodes 문제 내용 주어진 Node를 모두 Visite하는데 얼마의 step이 필요한가? 각 Node는 중복으로 방문이 가능하다. 접근 방법 개인적으로 이해하는데 시간을 오래 끌었다. Youtube나 google을 조회해 봐도 Floyd-Warshall 알고리즘이나 Dijkstra 를 이용한 방법이 검색되었다. 한마디로 이해하기 어렵고 주어진 시간내에 개발하기도 어려웠다. 그래서 Discussion을 찾아보는데 Smart BFS를 사용한 방법으로 본 문제를 풀었다는 이야기를 많이 보았다. 그래서 여기서 말하는 Smart BFS가 무었인지 알아보고 이를 통해서 문제를 풀어보고자 한다. BFS 접근 방법 BFS는 queue를 이용해서 접근 범위를 넓혀가는 방..

DFS 또는 Backtracking을 하거나 하는 방식으로 문제를 풀게 되면, 완전검색(Exhaustive Search)을 고려하게 된다. 처음 문제를 보았을때 이것이 완전검색을 원하는 것인지 아니면 최적의 P를 찾아낼 수 있는지를 판단하는 것이 중요하다. 가장 쉬운 판단법은 전제사항을 유심히 보는 것이다. 대부분 문제를 보면 숫자의 범위가 0에서 100,000이상의 범위를 갖게 된다. 그런데 이 문제만 이상하게 24, 32이런식으로 매우 작은 수로 범위를 갖는 경우가 나타난다. 이럴때는 완전검색을 고려해볼 필요가있다. 문제를 하나 풀어보면서 Masking과 DP를 어떻게 활용하는지 같이 알아보자. https://leetcode.com/problems/partition-to-k-equal-sum-subs..