문제 링크

내 코드

이걸 어떻게 라고 했지만, 생각보다 board가 크지 않아 bfs 할 만할 것 같았음.

2 x 3 $\Rightarrow$ 숫자로 만들기.

$6^0$	$6^1$	$6^2$
$6^3$	$6^4$	$6^5$

• 13ms, 17.80MB

class Solution {
public:
	int slidingPuzzle(vector<vector<int>>& board) {
		// 2 x 3 board => BFS
		// 1 6 6^2 
		// 6^3 6^4 6^5

		// max = 1 * 0 + 6 * 1 + 36 * 2 + 216 * 3 + 1296 * 4 + 7776 * 5 = 1 + 6 + 72 + 648 + 5184 + 38,880 = 44,791
		// 6^6 = 46,656

		const int SIZE = 46'656;
		vector visited(SIZE, 0);

		int initial = boardToNow(board);
		visited[initial] = 1;
		queue<int> q; q.push(initial);

		while (!q.empty()) {
			int now = q.front(); q.pop();

			vector nowBoard(2, vector(3, 0));
			nowToBoard(nowBoard, now);

			for (int i{}; i < 2; ++i) {
				for (int j{}; j < 3; ++j) {
					if (nowBoard[i][j]) continue;

					// 빈칸인 경우 다음 상태 갱신해서 계산

					for (int d{}; d < 4; ++d) {
						int ni = i + "0211"[d] - '1', nj = j + "1102"[d] - '1';
						if (ni < 0 || ni >= 2 || nj < 0 || nj >= 3) continue;
						// new board
						swap(nowBoard[i][j], nowBoard[ni][nj]);

						int next = boardToNow(nowBoard);
						swap(nowBoard[i][j], nowBoard[ni][nj]); // 원복 필요

						if (visited[next]) continue;
						visited[next] = visited[now] + 1;
						q.push(next);
					}

				}
			}
		}

		// answer
		// 1 * 1 + 6 * 2 + 36 * 3 + 216 * 4 + 1296 * 5 = 7465
		const int answer = 7465;

		if (!visited[answer]) return -1;
		return visited[answer] - 1;
	}

private:
	int boardToNow(vector<vector<int>>& board) {
		int now{}, place{ 1 };
		for (auto& row : board) {
			for (int val : row) {
				now += place * val;
				place *= 6;
			}
		}
		return now;
	}

	void nowToBoard(vector<vector<int>>& board, int now) {
		const int place = 6;
		for (auto& row : board) {
			for (int& val : row) {
				val = now % place;
				now /= place;
			}
		}
	}

};

Solution

Approach 1: Depth-First Search (DFS)

• 109ms, 12.34MB
• Complexity
  • Let m be the number of rows and n be the number of columns of the board.
  • Time Complexity: $O((m \cdot n)! \times {(m \cdot n)}^2)$
  • Space Complexity: $O((m \cdot n)!)$

class Solution {
private:
    // Direction map for zero's possible moves in a flattened 1D array (2x3
    // board)
    vector<vector<int>> directions = {
		{1, 3}, {0, 2, 4}, {1, 5},
        {0, 4}, {3, 5, 1}, {4, 2}
	};

public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // Convert the 2D board into a string representation to use as state
        string startState;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                startState += to_string(board[i][j]);
            }
        }

        // Map to store the minimum moves for each visited state
        unordered_map<string, int> visited;

        // Start DFS traversal from initial board state
        dfs(startState, visited, startState.find('0'), 0);

        // Return the minimum moves required to reach the target state, or -1 if
        // unreachable
        return visited.count("123450") ? visited["123450"] : -1;
    }

private:
    void dfs(string state, unordered_map<string, int>& visited, int zeroPos,
             int moves) {
        // Skip if this state has been visited with fewer or equal moves
        if (visited.count(state) && visited[state] <= moves) {
            return;
        }
        visited[state] = moves;

        // Try moving zero to each possible adjacent position
        for (int nextPos : directions[zeroPos]) {
            swap(state[zeroPos], state[nextPos]);  // Swap to generate new state
            dfs(state, visited, nextPos,
                moves + 1);  // Recursive DFS with updated state and move count
            swap(state[zeroPos],
                 state[nextPos]);  // Swap back to restore original state
        }
    }
};

Approach 2: Breadth-First Search (BFS)

• 3ms, 10.67MB
• Complexity
  • Let m be the number of rows and n be the number of columns of the board.
  • Time Complexity: $O((m \cdot n)! \times (m \cdot n))$
  • Space Complexity: $O((m \cdot n)!)$

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // Direction map for zero's possible moves in a 1D representation of the
        // 2x3 board
        vector<vector<int>> directions = {
			{1, 3}, {0, 2, 4}, {1, 5},
            {0, 4}, {1, 3, 5}, {2, 4}
		};

        string target = "123450";
        string startState;

        // Convert the 2D board into a string representation
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                startState += to_string(board[i][j]);
            }
        }

        unordered_set<string> visited;  // To store visited states
        queue<string> queue;
        queue.push(startState);
        visited.insert(startState);

        int moves = 0;

        // BFS to find the minimum number of moves
        while (!queue.empty()) {
            int size = queue.size();
            while (size-- > 0) {
                string currentState = queue.front();
                queue.pop();

                // Check if we reached the target solved state
                if (currentState == target) {
                    return moves;
                }

                int zeroPos = currentState.find('0');
                for (int newPos : directions[zeroPos]) {
                    string nextState = currentState;
                    swap(nextState[zeroPos], nextState[newPos]);

                    // Skip if this state has been visited
                    if (visited.count(nextState)) continue;

                    // Mark the new state as visited and add it to the queue
                    visited.insert(nextState);
                    queue.push(nextState);
                }
            }
            moves++;
        }
        return -1;
    }
};