[백준1525] 퍼즐

 

• 주어진 한칸이 비어있는 숫자 옮기기 퍼즐을 풀어 최종 상태를 만들때 까지 필요한 최소 이동횟수를 구하는 문제이다.

123

456

78*

최종 상태

step1 . Brute Force

• 가장 단순하게 재귀적으로 생각해보자. 현재 상태의 최소 이동 횟수는 한칸을 이동 후 최소 이동 횟수에 1을 더한 값이다.

(최소 이동 횟수) = 1 + (한칸 이동후 최소 이동횟수)

 

• 간단한 DFS 알고리즘이다! 하지만 이렇게 풀면 무한루프에 빠지게된다. 만약 최종상태를 만들 수 없는 입력값이 주어질 경우 재귀를 멈출 기저조건이 없기 때문에 무한루프를 돈다.
• 또한 만약 가능한 입력값이 입력돼도 한번 이동할때마다 최대 4번의 연산이 필요하므로 시간복잡도가 4의 지수배로 커진다. 즉, 15번이상만 이동해도 4^15이 되어 시간초과가 발생한다.

 

step2. 반복 없애기

• 9칸 퍼즐에서 숫자가 이동하다 보면 같은 배열 상태가 여러번 반복될 수 있다는 것은 직관적을 이해할 수 있다.
• 반복을 없애기 위해 다이나믹 프로그래밍(DP)을 구현해야 한다.
• 문제는 어떻게 dp를 구현할 것인가 이다.

 

step3. dp 구현

int dp[9][9][9][9][9][9][9][9][9];

 

• 직관적으로 각 칸을 각 인덱스로 변환하여 저장할 수 있다. 보기에 쫌(?) 그렇긴 하지만,,,
• 단순하고 직관적을 코드를 구현할 순 있겠지만 9^9개의 integer를 저장하면 위 문제에서는 당연히 메모리 초과가 발생한다.
• 퍼즐의 상태의 경우의 수는 9! = 약 30만개이다. 그리고 문제를 풀다보면 깨달았겠지만 딱 이 경우만 dp로 관리해야한다. idea1 처럼 단순하다는 것을 이유로 추가적인 메모리를 사용할 경우 가차없이 메모리 초과가 발생한다.

 

map<string, int> dp;

• 배열을 그상태로 저장할 수는 없으므로 문자열로 변환한다.

        123 → "123456780"

        456

        78*

• 퍼즐의 상태 문자열을 키, 해당 상태에 대한 최소 이동횟수를 값으로 갖는 map이다.
• 동적 프로그래밍은 아마 아래와 같이 구현 될 것이다.

int solution(int** board) {
		// 2차원 배열 board의 수열을 문자열로 변환
		string s = toString(board);
		if (dp.find(s) != dp.end()) return dp.find(s);
		
		int ret = 0;

		/*
			숫자를 이동하는 코드...
		*/

		dp.insert({s, ret});
		return ret;
}

• 코드를 보면 입력 상태(board)가 이미 구해진 값이라면 해당 값을 출력하고 아닐 경우 재귀를 돌린다.
• 이 코드 역시 틀린다. 이유가 뭘까?
• 바로 이전에 구한 값이 최소가 아닐 수 있기 때문이다.

이즘음에서 근본적인 문제를 아마 발견했을 것이다. 바로 이문제는 DFS로 푸는 것이 매우 어렵다,,,

최소 이동횟수를 구하는 문제로 tree로 생각하면 최소 깊이를 구하는 문제이다. 즉, 이 문제는 BFS로 푸는것이 더 효율적이다.

step3. BFS

• BFS는 DFS때처럼 메모리에 이동횟수를 저장해 놓을 필요가 없다. 왜냐하면 BFS 특성상 이전 시점에 구한 이동횟수는 반드시 현재 시점보다 같거나 작을 수 밖에 없다.
• 그러므로 만약 현재의 퍼즐 상태가 이미 이전에 구한 상태라면 구할 필요가 없다.
• 즉, 메모리에는 이미 계산한 값이라는 기록만 남기면 된다. 그러므로 set 자료형이 적당하겠다. ****
• 위와 마찬가지로 set에는 퍼즐 배열을 문자열로 변환해 저장한다.

Solution

int solution() {
    
    set<int> s;
    queue<string> q;
    queue<int> cnt;
    
    vector<vector<int>> v(3,vector<int>(3));
    int x, y;
    
    for (int i=0; i<3; ++i) {
        for (int j=0; j<3; ++j) {
            cin >> v[i][j];
            if (v[i][j]==0) x=i; y=j;
        }
    }
    
    string s0 = toString(v);
    // cout << s0 << endl;
    
    q.push(s0);
    cnt.push(0);
    s.insert(stoi(s0));
    int ret = -1;
    
    while (!q.empty()) {
        string curr = q.front();
        q.pop();
        int curr_cnt = cnt.front();
        cnt.pop();
        
				// 현재 상태가 최종상태면 최소 이동횟수 출력
        if (curr == "123456780") {
            ret = curr_cnt; 
            break;
        }
        
        
				
        vector<vector<int>> arr = toArray(curr);
        
        int cx, cy;
        
        for (int i=0; i<3; ++i) {
            for (int j=0; j<3; ++j) {
                if (arr[i][j] == 0)  { 
                    cx=i; 
                    cy=j;
                    break;
                }
            }
        }

				// 숫자 이동
        for (int i=0; i<4; ++i) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
            
            arr[cx][cy] = arr[nx][ny];
            arr[nx][ny] = 0;
            
            string next = toString(arr);
            
						// 현재 상태가 이전에 조사 안한 상태인 경우
            if (s.find(stoi(next)) == s.end()) {
                s.insert(stoi(next));
                q.push(next);
                cnt.push(curr_cnt+1);
            }
            
            arr[nx][ny] = arr[cx][cy];
            arr[cx][cy] = 0;
        }
        
    }
    
    return ret;
    
}