[프로그래머스][JAVA] 84021. 퍼즐조각채우기

💡 문제
퍼즐조각채우기(https://school.programmers.co.kr/learn/courses/30/lessons/84021)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

---

🤓 문제 풀이

문제 설명

주어진 문제는 게임 보드의 빈 공간에 테이블 위의 퍼즐 조각을 적절히 놓아서 최대한 많은 칸을 채우는 것입니다. 퍼즐 조각을 회전시킬 수는 있지만 뒤집을 수는 없습니다. 각 퍼즐 조각은 인접한 칸이 비어있으면 안 됩니다.

---

문제 접근 방법

• 퍼즐 조각 추출:
  • BFS를 사용하여 테이블에서 퍼즐 조각을 추출합니다.
  • 퍼즐 조각을 추출할 때, 모든 가능한 회전을 고려하여 저장합니다.
• 빈 공간 추출:
  • BFS를 사용하여 게임 보드에서 빈 공간을 추출합니다.
• 퍼즐 조각 맞추기:
  • 각 빈 공간에 대해 모든 퍼즐 조각을 시도하여 맞춰봅니다.
  • 맞는 퍼즐 조각이 있다면 해당 퍼즐 조각을 게임 보드에서 사용하고, 사용한 퍼즐 조각을 테이블에서 제거합니다.
  • 모든 가능한 경우를 탐색하여 최대한 많은 칸을 채우도록 합니다.

---

BFS 선택 이유

BFS는 시작점에서 인접한 노드를 차례대로 방문하며 탐색하는 방법입니다. 이 문제에서는 두 가지 이유로 BFS를 사용했습니다

BFS는 시작점에서 인접한 노드를 차례대로 방문하며 탐색하는 방법으로, 이 문제에서는 연결된 영역을 추출하는 데 효과적입니다. BFS를 통해 퍼즐 조각이나 빈 공간의 모든 연결된 칸을 효율적으로 탐색하고, 정규화된 형태로 저장할 수 있습니다. 이를 통해 회전 및 비교 과정에서 용이하게 사용할 수 있습니다.

1. 연결된 영역 추출:
   • 게임 보드와 테이블에서 연결된 빈 공간이나 퍼즐 조각을 추출하기 위해 BFS를 사용했습니다. BFS는 시작점에서 인접한 노드를 차례대로 방문하므로, 연결된 영역을 효율적으로 탐색할 수 있습니다.
2. 정규화된 형태 추출:
   • BFS를 사용하여 추출한 퍼즐 조각과 빈 공간을 정규화된 형태로 저장하면, 이를 회전시켜 비교할 때 쉽게 처리할 수 있습니다. BFS를 통해 얻은 좌표를 기준으로 정규화하면, 회전 및 비교가 용이해집니다.

DFS 사용

DFS는 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식으로, 이 문제에서는 연결된 영역을 추출하는 데 효과적입니다. DFS를 통해 퍼즐 조각이나 빈 공간의 모든 연결된 칸을 효율적으로 탐색하고, 정규화된 형태로 저장할 수 있습니다. 이를 통해 회전 및 비교 과정에서 용이하게 사용할 수 있습니다.

---

구현코드

1) BFS를 사용한 구현코드

import java.util.*;

class Solution {
    // 상, 하, 좌, 우로 이동하기 위한 방향 배열
    private final int[] dx = {-1, 1, 0, 0};
    private final int[] dy = {0, 0, -1, 1};

    public int solution(int[][] game_board, int[][] table) {
        // 게임 보드에서 빈 공간을 추출
        List<List<int[]>> emptySpaces = extractShapes(game_board, 0);
        // 테이블에서 퍼즐 조각을 추출
        List<List<int[]>> puzzlePieces = extractShapes(table, 1);

        // 퍼즐 조각을 빈 공간에 맞춰보는 과정
        boolean[] used = new boolean[puzzlePieces.size()];
        int filled = 0;

        for (List<int[]> space : emptySpaces) {
            for (int i = 0; i < puzzlePieces.size(); i++) {
                if (used[i]) continue;
                if (isMatch(space, puzzlePieces.get(i))) {
                    used[i] = true;
                    filled += space.size();
                    break;
                }
            }
        }

        return filled;
    }

    // BFS를 사용하여 도형(빈 공간 또는 퍼즐 조각)을 추출
    private List<List<int[]>> extractShapes(int[][] board, int target) {
        int n = board.length;
        boolean[][] visited = new boolean[n][n];
        List<List<int[]>> shapes = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && board[i][j] == target) {
                    List<int[]> shape = new ArrayList<>();
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;

                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        shape.add(cell);
                        for (int d = 0; d < 4; d++) {
                            int nx = cell[0] + dx[d];
                            int ny = cell[1] + dy[d];
                            if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && board[nx][ny] == target) {
                                queue.add(new int[]{nx, ny});
                                visited[nx][ny] = true;
                            }
                        }
                    }

                    // 도형을 좌상단 기준으로 정규화하고 모든 회전을 생성
                    shapes.add(normalizeShape(shape));
                }
            }
        }

        return shapes;
    }

    // 도형을 좌상단 기준으로 정규화하고 모든 회전을 생성
    private List<int[]> normalizeShape(List<int[]> shape) {
        List<int[]> normalized = new ArrayList<>();
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;

        for (int[] cell : shape) {
            minX = Math.min(minX, cell[0]);
            minY = Math.min(minY, cell[1]);
        }

        for (int[] cell : shape) {
            normalized.add(new int[]{cell[0] - minX, cell[1] - minY});
        }

        Collections.sort(normalized, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
        return normalized;
    }

    // 두 도형이 일치하는지 확인 (모든 회전을 시도)
    private boolean isMatch(List<int[]> space, List<int[]> piece) {
        for (int rot = 0; rot < 4; rot++) {
            if (space.size() == piece.size() && match(space, piece)) {
                return true;
            }
            piece = rotateShape(piece);
        }
        return false;
    }

    // 도형을 시계 방향으로 90도 회전
    private List<int[]> rotateShape(List<int[]> shape) {
        List<int[]> rotated = new ArrayList<>();
        for (int[] cell : shape) {
            rotated.add(new int[]{cell[1], -cell[0]});
        }

        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        for (int[] cell : rotated) {
            minX = Math.min(minX, cell[0]);
            minY = Math.min(minY, cell[1]);
        }

        for (int[] cell : rotated) {
            cell[0] -= minX;
            cell[1] -= minY;
        }

        Collections.sort(rotated, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
        return rotated;
    }

    // 두 도형이 동일한지 확인
    private boolean match(List<int[]> space, List<int[]> piece) {
        for (int i = 0; i < space.size(); i++) {
            if (space.get(i)[0] != piece.get(i)[0] || space.get(i)[1] != piece.get(i)[1]) {
                return false;
            }
        }
        return true;
    }
}

2) DFS를 사용한 구현코드

import java.util.*;

class Solution {
    // 상, 하, 좌, 우로 이동하기 위한 방향 배열
    private final int[] dx = {-1, 1, 0, 0};
    private final int[] dy = {0, 0, -1, 1};

    public int solution(int[][] game_board, int[][] table) {
        // 게임 보드에서 빈 공간을 추출
        List<List<int[]>> emptySpaces = extractShapes(game_board, 0);
        // 테이블에서 퍼즐 조각을 추출
        List<List<int[]>> puzzlePieces = extractShapes(table, 1);

        // 퍼즐 조각을 빈 공간에 맞춰보는 과정
        boolean[] used = new boolean[puzzlePieces.size()];
        int filled = 0;

        for (List<int[]> space : emptySpaces) {
            for (int i = 0; i < puzzlePieces.size(); i++) {
                if (used[i]) continue;
                if (isMatch(space, puzzlePieces.get(i))) {
                    used[i] = true;
                    filled += space.size();
                    break;
                }
            }
        }

        return filled;
    }

    // DFS를 사용하여 도형(빈 공간 또는 퍼즐 조각)을 추출
    private List<List<int[]>> extractShapes(int[][] board, int target) {
        int n = board.length;
        boolean[][] visited = new boolean[n][n];
        List<List<int[]>> shapes = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && board[i][j] == target) {
                    List<int[]> shape = new ArrayList<>();
                    dfs(board, visited, shape, i, j, target);
                    shapes.add(normalizeShape(shape));
                }
            }
        }

        return shapes;
    }

    // DFS 함수
    private void dfs(int[][] board, boolean[][] visited, List<int[]> shape, int x, int y, int target) {
        int n = board.length;
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{x, y});
        visited[x][y] = true;

        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            shape.add(cell);
            for (int d = 0; d < 4; d++) {
                int nx = cell[0] + dx[d];
                int ny = cell[1] + dy[d];
                if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && board[nx][ny] == target) {
                    stack.push(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

    // 도형을 좌상단 기준으로 정규화하고 모든 회전을 생성
    private List<int[]> normalizeShape(List<int[]> shape) {
        List<int[]> normalized = new ArrayList<>();
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;

        for (int[] cell : shape) {
            minX = Math.min(minX, cell[0]);
            minY = Math.min(minY, cell[1]);
        }

        for (int[] cell : shape) {
            normalized.add(new int[]{cell[0] - minX, cell[1] - minY});
        }

        Collections.sort(normalized, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
        return normalized;
    }

    // 두 도형이 일치하는지 확인 (모든 회전을 시도)
    private boolean isMatch(List<int[]> space, List<int[]> piece) {
        for (int rot = 0; rot< 4; rot++) {
            if (space.size() == piece.size() && match(space, piece)) {
                return true;
            }
            piece = rotateShape(piece);
        }
        return false;
    }

    // 도형을 시계 방향으로 90도 회전
    private List<int[]> rotateShape(List<int[]> shape) {
        List<int[]> rotated = new ArrayList<>();
        for (int[] cell : shape) {
            rotated.add(new int[]{cell[1], -cell[0]});
        }

        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        for (int[] cell : rotated) {
            minX = Math.min(minX, cell[0]);
            minY = Math.min(minY, cell[1]);
        }

        for (int[] cell : rotated) {
            cell[0] -= minX;
            cell[1] -= minY;
        }

        Collections.sort(rotated, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
        return rotated;
    }

    // 두 도형이 동일한지 확인
    private boolean match(List<int[]> space, List<int[]> piece) {
        for (int i = 0; i < space.size(); i++) {
            if (space.get(i)[0] != piece.get(i)[0] || space.get(i)[1] != piece.get(i)[1]) {
                return false;
            }
        }
        return true;
    }
}

---

📚 풀이 보완

코드 설명

BFS 코드 설명

• 퍼즐 조각 및 빈 공간 추출:
  • extractShapes 메서드를 사용하여 게임 보드의 빈 공간과 테이블의 퍼즐 조각을 BFS를 이용해 추출합니다.
  • BFS는 큐를 사용하여 인접한 칸을 탐색하며, 각 연결된 영역을 리스트에 저장합니다.
  • 각 추출된 조각과 빈 공간을 좌상단 기준으로 정규화하여 저장합니다.
• 퍼즐 조각 맞추기:
  • isMatch 메서드를 사용하여 각 빈 공간에 대해 모든 퍼즐 조각을 시도합니다.
  • 퍼즐 조각을 90도씩 회전시키며 맞는지 확인합니다.
  • 맞는 퍼즐 조각을 찾으면 해당 퍼즐 조각을 사용하고 사용한 퍼즐 조각을 테이블에서 제거합니다.
• 결과 반환:
  • 최종적으로 최대한 많은 칸을 채울 수 있는 경우의 수를 반환합니다.

요약

• BFS를 사용하여 퍼즐 조각과 빈 공간을 추출하고, 이를 정규화하여 비교합니다.
• 각 퍼즐 조각을 회전시키며 빈 공간에 맞춰보고, 맞는 경우를 찾습니다.
• 최종적으로 최대한 많은 칸을 채우는 방법을 찾아 그 결과를 반환합니다.

DFS 코드 설명

• 빈 공간 및 퍼즐 조각 추출:
  • DFS를 사용하여 게임 보드와 테이블에서 연결된 빈 공간과 퍼즐 조각을 추출합니다.
  • 추출된 도형을 좌상단 기준으로 정규화하여 저장합니다.
• 퍼즐 조각 맞추기:
  • 각 빈 공간에 대해 모든 퍼즐 조각을 시도해 봅니다.
  • 퍼즐 조각을 90도씩 회전시키며 빈 공간에 맞는지 확인합니다.
  • 맞는 퍼즐 조각을 찾으면 해당 퍼즐 조각을 사용하고, 사용한 퍼즐 조각을 테이블에서 제거합니다.
• 최종 결과 반환:
  • 최종적으로 최대한 많은 칸을 채우는 방법을 찾아 그 결과를 반환합니다.

---

📍 Plus+

BFS 시간 복잡도와 공간 복잡도 분석

시간 복잡도

• 퍼즐 조각을 추출하는데 O(n^2) 시간이 걸리며, 이를 최대 n번 (퍼즐 조각의 최대 수) 반복합니다.
• 퍼즐 조각을 회전시키며 비교하는데 O(n^2) 시간이 걸립니다.
• 전체적으로 최악의 경우 O(n^4)의 시간 복잡도를 가집니다.

공간 복잡도

• 추가로 사용되는 공간은 추출된 퍼즐 조각과 빈 공간을 저장하는 리스트로 O(n^2)입니다.
• 회전된 퍼즐 조각을 저장하는데 O(n^2) 공간이 추가로 필요합니다.
• 따라서, 전체 공간 복잡도는 O(n^2)입니다.

요약

• BFS를 사용하여 퍼즐 조각과 빈 공간을 추출하고, 이를 정규화하여 비교합니다.
• 각 퍼즐 조각을 회전시키며 빈 공간에 맞춰보고, 맞는 경우를 찾습니다.
• 최종적으로 최대한 많은 칸을 채우는 방법을 찾아 그 결과를 반환합니다.

요약

• 시간 복잡도: O(n^2)
• 공간 복잡도: O(n^2)

---

BFS와 DFS를 사용한 문제 풀이 - 장단점, 차이점

BFS(너비 우선 탐색)

장점

• 최단 경로 찾기: BFS는 가장 먼저 발견된 경로가 최단 경로임을 보장하므로, 최단 경로를 찾는 문제에서 유리합니다.
• 균등한 탐색: 동일 깊이의 노드들을 모두 탐색하고 난 후에 다음 깊이로 넘어가므로, 노드의 특정 깊이까지의 탐색이 필요할 때 적합합니다.

단점

• 메모리 사용량: BFS는 큐를 사용하여 각 레벨의 노드들을 저장하므로, 깊이가 깊어질수록 큐에 많은 노드가 쌓여 메모리 사용량이 증가합니다.
• 복잡한 문제에 비효율적: 노드 수가 많은 경우, 큐의 크기가 기하급수적으로 커질 수 있어 메모리 관리가 어려워집니다.

DFS(깊이 우선 탐색)

장점

• 메모리 효율성: DFS는 스택(혹은 재귀)을 사용하여 탐색하므로, 노드 수가 많더라도 메모리 사용량이 상대적으로 적습니다.
• 백트래킹: 특정 조건을 만족하는 경로를 찾는 문제에서 유리하며, 백트래킹을 통해 다양한 경로를 쉽게 탐색할 수 있습니다.

단점

• 무한 탐색: 깊이가 무한히 깊어질 수 있는 그래프에서는 종료 조건을 잘못 설정하면 무한 루프에 빠질 수 있습니다.
• 최단 경로 보장 불가: DFS는 첫 번째로 발견된 경로가 최단 경로임을 보장하지 않으므로, 모든 경로를 탐색해야 하는 경우 비효율적일 수 있습니다.

---

두 알고리즘의 차이점

• 탐색 방식: BFS는 너비를 우선으로 탐색하여 같은 깊이의 모든 노드를 탐색한 후 다음 깊이로 넘어가고, DFS는 깊이를 우선으로 탐색하여 하나의 경로를 끝까지 탐색한 후 다음 경로로 이동합니다.
• 자료구조: BFS는 큐(Queue)를 사용하고, DFS는 스택(Stack) 또는 재귀(Recursive)를 사용합니다.
• 경로의 특성: BFS는 최단 경로를 보장하지만 메모리 사용량이 많고, DFS는 메모리 사용량이 적지만 최단 경로를 보장하지 않습니다.

---

해당 문제에 최적화된 자료구조

해당 문제는 게임 보드와 테이블에서 연결된 빈 공간과 퍼즐 조각을 추출하는 문제입니다. 이 과정에서는 연결된 컴포넌트를 효율적으로 탐색하고, 이를 정규화하여 비교해야 합니다. 두 탐색 방법 모두 사용 가능하지만, DFS가 이 문제에 더 적합할 수 있습니다.

이유

• 메모리 효율성: 문제의 제한사항(최대 50x50 격자)을 고려할 때, DFS는 상대적으로 적은 메모리 사용으로 각 도형을 추출할 수 있습니다.
• 간단한 구현: DFS는 스택 또는 재귀 호출을 사용하여 간단하게 구현할 수 있으며, 각 도형의 추출 과정이 명확해집니다.

---

문제 유형에 따른 자료구조 선택

• 최단 경로 탐색: BFS가 유리합니다. 예를 들어, 미로 탐색 문제에서 출발점부터 도착점까지의 최단 경로를 찾는 경우.
• 모든 경로 탐색 및 백트래킹: DFS가 유리합니다. 예를 들어, 특정 조건을 만족하는 모든 경로를 찾거나, 퍼즐 조각을 추출하는 문제에서.
• 공간 효율성: DFS가 메모리 사용량이 적어 유리합니다. 예를 들어, 그래프의 깊이가 깊고, 노드의 개수가 많은 경우.
• 복잡한 그래프 구조: BFS는 깊이가 깊지 않은 경우에 유리하며, DFS는 깊이가 깊고 복잡한 구조를 탐색할 때 유리합니다.

따라서, 문제의 특성과 요구사항에 따라 BFS와 DFS를 적절히 선택하여 사용해야 한다고 생각합니다.. 특정 문제에서는 두 가지 방법을 모두 시도해보고, 효율성을 비교하여 최적의 방법을 선택하는 것이 중요합니다.