백준 1525번 퍼즐 BFS 최단,최소 문제. DFS는 힘든이유..
퍼즐 문제는 메모리가 매우 적게 제한된 문제이다. 보통 최단문제의 경우 BFS로 접근하는게 일반적이지만, BFS의 경우 매 단계마다 가능한 경우의 수를 모두 queue에 저장해야되므로 상태를 저장해야되는 맵정보를 처음에 vector로한 결과 메모리가 초과되는 문제가 있었다. 그래서, 한번에 최대깊이까지만,,, 최대 메모리를 사용하고, 그 이상으로 메모리를 사용하지 않는 DFS로 접근을 시도했다. DFS의 경우, map정보를 전역 혹은, 매개변수를 포인터로 넘겨주고, return시에 다시 맵을 원상복귀 시켜주기만 한다면, DFS의 깊이와 상관없이 map 한개의 메모리양만 사용하게 설계할 수 있다. 하지만 이 문제는 기본적으로 DFS로 접근이 힘들다. 1. DFS특성상 최단문제에 적합하지 않다. 그 이유로는..
2020. 3. 22.
