BackTracking1 BOJ2549 루빅의 사각형 2549번 루빅의 사각형 4×4 격자판이 있다. 행을 한 개 골라 아래쪽으로 k번(1≤k≤3) 움직이거나 열을 한 개 골라 오른쪽으로 k번(1≤k≤3) 움직이는 것을 한 번 움직인다고 한다. 격자판의 숫자가 주어질 때, 최소 횟수로 격자판을 움직여 1부터 16까지 순서대로 배열된 격자판으로 만드는 횟수(≤7)와 방법을 출력한다. 일단은, 되는대로 BFS를 돌려봤지만 역시 메모리 초과로 통과할 수 없었다. 한 번 움직이는 경우의 수는 8(행/열 개수)*3(k 개수)였고 아무리 정답이 7번 이내로 나온다 해도 24^7개의 경우를 확인하려니 당연히,, 몇 가지 최적화로 가짓수를 줄여봤지만 그래도 메모리초과였다. 방법 1. BFS + 양방향 탐색 + map BFS로 찾되 양방향으로 탐색하기로 했다. 주어진 상태.. 2021. 7. 25. 이전 1 다음
