[코테연습] 773. Sliding Puzzle

https://leetcode.com/problems/sliding-puzzle/description/?envType=daily-question&envId=2024-11-25

문제 타입

• 그래프 탐색 (BFS)
• 상태 공간 탐색
• 퍼즐 문제

문제 분석

• 주어진 2x3 슬라이딩 퍼즐에서 숫자 '0'은 빈 칸을 나타내며, 목표는 퍼즐의 초기 상태를 '123450' 형태로 바꾸는 것입니다.
• BFS를 사용해 최단 경로 탐색 문제로 접근해야 합니다.
• 각 상태에서 이동 가능한 위치로 빈 칸을 이동시키며 목표 상태에 도달하기 위한 최소 이동 횟수를 찾아야 합니다.

문제 풀이

• 초기 상태를 문자열로 변환하여 큐에 저장하고, BFS로 탐색을 진행합니다.
• 각 노드에서는 '0'이 이동할 수 있는 위치를 계산하여 새로운 퍼즐 상태를 만듭니다.
• 새로운 상태가 방문되지 않았으면 큐에 추가하고, 목표 상태에 도달하면 현재 이동 횟수를 반환합니다.
• 목표 상태를 찾지 못하고 큐가 빌 때까지 진행하면 -1을 반환합니다.

 

> java

 

class Solution {
    public int slidingPuzzle(int[][] board) {
        // 이동 방향을 정의 (아래, 위, 오른쪽, 왼쪽)
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        // 목표 상태 ("123450")
        String target = "123450";
        StringBuilder start = new StringBuilder();
        int zeroX = 0, zeroY = 0;

        // 초기 상태를 문자열로 변환하고, 0의 위치를 기록
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                start.append(board[i][j]);
                if (board[i][j] == 0) {
                    zeroX = i;
                    zeroY = j;
                }
            }
        }

        // BFS를 위한 큐와 방문한 상태를 기록할 집합
        Queue<Node> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        // 초기 상태를 큐에 추가하고 방문 기록에 추가
        queue.offer(new Node(start.toString(), zeroX, zeroY));
        visited.add(start.toString());

        int steps = 0; // 움직임 횟수

        // BFS 탐색 시작
        while (!queue.isEmpty()) {
            int size = queue.size();

            // 현재 레벨의 모든 노드를 탐색
            for (int i = 0; i < size; i++) {
                Node current = queue.poll();

                // 현재 상태가 목표 상태와 같은지 확인
                if (current.board.equals(target)) {
                    return steps;
                }

                // 0의 현재 위치를 가져옴
                int x = current.zeroX;
                int y = current.zeroY;

                // 4가지 방향으로 이동을 시도
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];

                    // 새로운 위치가 보드 범위 내에 있는지 확인
                    if (nx >= 0 && nx < 2 && ny >= 0 && ny < 3) {
                        // 새로운 보드 상태를 생성 (0과 새로운 위치 교환)
                        String nextBoard = swap(current.board, x, y, nx, ny);
                        // 방문하지 않은 상태라면 큐에 추가하고 방문 기록에 추가
                        if (!visited.contains(nextBoard)) {
                            visited.add(nextBoard);
                            queue.offer(new Node(nextBoard, nx, ny));
                        }
                    }
                }
            }
            steps++; // 현재 레벨 탐색이 끝났으므로 움직임 횟수 증가
        }

        return -1; // 목표 상태에 도달할 수 없는 경우
    }

    // 두 위치의 문자를 교환하여 새로운 보드 상태 문자열을 반환하는 메소드
    private String swap(String board, int x1, int y1, int x2, int y2) {
        char[] chars = board.toCharArray();
        int index1 = x1 * 3 + y1;
        int index2 = x2 * 3 + y2;

        // 두 위치의 값을 교환
        char temp = chars[index1];
        chars[index1] = chars[index2];
        chars[index2] = temp;

        return new String(chars);
    }

    // 보드 상태와 0의 위치를 저장하는 클래스
    class Node {
        String board; // 현재 보드 상태를 문자열로 저장
        int zeroX, zeroY; // 0의 위치를 저장

        public Node(String board, int zeroX, int zeroY) {
            this.board = board;
            this.zeroX = zeroX;
            this.zeroY = zeroY;
        }
    }
}

 

> python

 

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # 초기 상태를 문자열로 변환
        start = ''.join(str(num) for row in board for num in row)
        target = '123450'
        # 각 위치에서 이동 가능한 인덱스를 정의
        neighbors = {
            0: [1, 3], 1: [0, 2, 4], 2: [1, 5],
            3: [0, 4], 4: [1, 3, 5], 5: [2, 4]
        }
        
        # BFS를 위한 큐와 방문 기록
        queue = deque([(start, 0)])  # (현재 상태 문자열, 현재까지의 움직임 수)
        visited = set([start])  # 방문한 상태를 기록하기 위한 집합
        
        while queue:
            state, steps = queue.popleft()  # 큐에서 현재 상태를 꺼냄
            if state == target:
                return steps  # 목표 상태에 도달하면 움직임 수를 반환
            
            # 0의 현재 위치 찾기
            zero_idx = state.index('0')
            
            # 가능한 이동에 대해 탐색
            for neighbor in neighbors[zero_idx]:
                # 현재 상태에서 0과 이웃한 숫자를 교환하여 새로운 상태 생성
                new_state = list(state)
                new_state[zero_idx], new_state[neighbor] = new_state[neighbor], new_state[zero_idx]
                new_state_str = ''.join(new_state)
                
                # 새로운 상태가 방문하지 않은 상태라면 큐에 추가
                if new_state_str not in visited:
                    visited.add(new_state_str)
                    queue.append((new_state_str, steps + 1))
        
        return -1  # 목표 상태에 도달할 수 없는 경우