프로그래머스 - 퍼즐 조각 채우기 (Java)

📌 문제 링크:
퍼즐 조각 채우기 - 프로그래머스

---

1. 문제 이해 및 접근 방식

🔹 문제 개요

• 빈칸(0)으로 이루어진 game_board가 주어지고, 퍼즐 조각(1)으로 이루어진 table이 주어진다.
• table에 있는 퍼즐 조각을 회전하여 game_board의 빈칸을 채울 수 있다.
• 최대한 많은 빈칸을 채울 때, 채운 칸의 개수를 반환하는 문제

---

2. 초기 접근 방식 및 문제점 (디버깅 과정)

🚨 1차 시도: Set<String>을 사용하여 퍼즐 비교

✔ 각 퍼즐을 DFS로 탐색한 후, 문자열(StringBuilder)로 변환하여 Set에 저장
✔ 회전 시 Set에 저장된 문자열과 비교하여 빈칸을 채우는 방식

❌ 문제점

• 동일한 모양의 퍼즐이 여러 개 있을 때, 각 퍼즐을 몇 개씩 사용할 수 있는지 추적하기 어려움.
• 퍼즐을 회전했을 때도 동일한 퍼즐로 인식해야 하지만, Set만 사용하면 회전된 상태를 고려할 수 없음.

---

🚨 2차 시도: Map<Integer, Set<String>>을 활용하여 회전된 퍼즐 관리

✔ 각 퍼즐 조각을 Map<Integer, Set<String>>으로 저장하여 개수 관리
✔ 퍼즐 회전 시 문자열 비교 후, 사용 가능한 퍼즐을 제거하는 방식

❌ 문제점

• DFS 탐색 과정에서 방향을 문자열로 저장할 때, "12"라는 문자열이 1 → 2로 탐색한 것인지, 1에서 재귀가 끝나고 다시 2로 이동한 것인지 구분할 수 없음.
• 즉, 탐색 경로를 문자열로 저장할 때 "재귀 순서"에 따른 중복 문제가 발생

---

🚨 3차 시도: DFS 탐색 경로의 끝을 명확히 하기 위해 문자열에 . 추가

✔ DFS 탐색 과정에서 sb.append(".")을 추가하여 탐색이 종료된 지점을 명확히 구분
✔ 탐색이 끝날 때마다 .을 붙이면 동일한 퍼즐의 탐색 경로를 유일하게 만들 수 있음.

❌ 문제점

• 퍼즐의 탐색 경로를 저장하는 방식은 개선되었지만,
  Set<String>을 사용하여 퍼즐을 비교하는 과정에서 같은 모양의 퍼즐을 중복으로 인식하는 문제가 남아 있음.
• 회전한 모든 퍼즐을 동일한 퍼즐로 인식하도록 개선 필요

---

🚨 4차 시도: 퍼즐을 라벨링하여 moveHistory에 저장

✔ 각 퍼즐 조각에 라벨을 부여하고, moveHistory[label]에 저장하여 중복 관리
✔ 각 퍼즐 조각을 4방향으로 회전하며 Set<String>에 저장하여 중복 제거

❌ 문제점

• game_board의 빈칸과 퍼즐 조각을 매칭하는 과정에서 퍼즐이 올바르게 채워지지 않는 버그 발생
• 퍼즐을 찾고 저장하는 과정과, 빈칸을 찾고 채우는 과정이 다르게 동작할 가능성

---

🚨 5차 시도: DFS를 수행한 후, Set<String>을 활용하여 퍼즐 회전 관리

✔ 각 퍼즐을 4번 회전하며 가능한 모든 모양을 Set<String>에 저장
✔ game_board에서 빈칸을 탐색할 때, moveHistory에서 일치하는 퍼즐을 찾아 사용

✅ 최종적으로 모든 퍼즐을 정확하게 빈칸에 맞출 수 있도록 최적화 완료! 🚀

---

3. 최종 코드 (Java)

import java.util.*;

class Solution {
    int[] dix = {-1, 0, 1, 0}; // 상, 우, 하, 좌
    int[] diy = {0, 1, 0, -1};
    
    Set<String>[] moveHistory;
    int n;
    StringBuilder sb = new StringBuilder();
    int answer = 0;
    int blockSize = 1;
    boolean[] isUsed;

    public int solution(int[][] game_board, int[][] table) {
        n = table.length;
        addLabel(table);
        moveHistory = new Set[blockSize + 1];
        for (int i = 0; i <= blockSize; i++) {
            moveHistory[i] = new HashSet<>();
        }
        isUsed = new boolean[blockSize + 1];

        // 회전하며 퍼즐 탐색 및 저장
        searchDownRight(table, 0);
        searchRightUp(table, 1);
        searchUpLeft(table, 2);
        searchLeftDown(table, 3);
        
        searchGameBoard(game_board);

        return answer / 2; // 좌표를 2배로 관리했으므로 나누기 2
    }

    private void addLabel(int[][] table) {
        boolean[][] visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (table[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    table[i][j] = blockSize;
                    labelDfs(i, j, 0, visited, table);
                    blockSize++;
                }
            }
        }
    }

    private void searchGameBoard(int[][] game_board) {
        boolean[][] visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (game_board[i][j] == 0 && !visited[i][j]) {
                    visited[i][j] = true;
                    dfs(i, j, 1, visited, game_board, 0);
                    String result = sb.toString();
                    sb.setLength(0);

                    for (int k = 1; k <= blockSize; k++) {
                        if (!isUsed[k] && moveHistory[k].contains(result)) {
                            isUsed[k] = true;
                            answer += result.length() + 2;
                            break;
                        }
                    }
                }
            }
        }
    }

    private void dfs(int x, int y, int wall, boolean[][] visited, int[][] table, int turn) {
        for (int i = 0; i < 4; i++) {
            int dx = x + dix[(i - turn + 4) % 4];
            int dy = y + diy[(i - turn + 4) % 4];
            if (dx < 0 || dy < 0 || dx >= n || dy >= n) continue;
            if (visited[dx][dy]) continue;
            if (table[dx][dy] == wall) continue;

            visited[dx][dy] = true;
            sb.append(i);
            dfs(dx, dy, wall, visited, table, turn);
            sb.append(".");
        }
    }
}

---

4. 결론 및 정리

✔ 퍼즐 조각을 DFS 탐색 후, 문자열(StringBuilder)로 저장하여 비교
✔ Set<String>을 사용하여 퍼즐 회전 시 중복 제거
✔ 각 퍼즐에 라벨을 부여하여 관리 (blockSize 활용)
✔ 빈칸을 탐색하여 퍼즐 조각과 매칭 후, 최적의 조합 찾기