잘하시는 분들은 어려움을 겪지 않았을 것이라 생각되지만, 혹시나 저와 같은 문제를 겪는 분들을 위해 제 생각을 남겨봅니다.

처음 이 문제를 풀었을 때, BitMasking + DP + BFS로 해결을 했습니다.

다만 BFS로 풀었을 때, 메모리 초과가 발생했습니다.

이를 해결하기 위해 DFS로 수정해 제출해 통과되었습니다.

DFS와 BFS에 따라 시간과 메모리에서 차이가 발생합니다.

YNYYNYYY => 10110111  이라고 할 때, 

BFS의 경우, 중복 탐색을 막아주지 않게 된다면

11110111 이 되기 위해서 queue에 1의 개수만큼 즉 6개가 queue에 들어가게 됩니다. < nxt := 다음 bit / now := 현재 bit / i := 1인 비트 index / j := 0인 비트 index[nxt비트에 추가될 위치]>

이를 해결하기 위해 단순히 현재 dp[nxt] > dp[now] + cost[i][j] 인 경우에만 queue에 들어가도록 변경해주더라도 6개에서 1개로 줄어들면서 

메모리, 시간 모두 통과가 됩니다.

다만 여전히 BFS와  DFS에 따라 시간 차이가 제 경우에는 아래와 같이 발생했습니다.

BFS : 4256ms                    DFS : 1956ms

추가로 Edge Case 하나 남깁니다.