[프로그래머스] 퍼즐 조각 채우기 (BFS)

문제 소개

오늘 풀었던 퍼즐 조각 채우기 - 프로그래머스 문제를 정리합니다.
이 문제는 2D 보드의 빈 공간과 퍼즐 조각의 모양을 맞춰 최대한 많은 조각을 채워 넣는 문제입니다.
문제의 핵심은 조각 회전이 가능하고 조각을 넣은 후 인접한 빈칸이 없어야 한다는 조건을 만족하며 퍼즐을 채우는 것입니다.

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

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 빈 공간과 퍼즐 조각을 각각 추출하여 별도의 리스트로 저장
2. 퍼즐 조각을 최대 4번 회전시키며 각 빈 공간에 정규화된 좌표 형태로 비교
3. 사용된 퍼즐은 중복 사용하지 않도록 체크
4. 일치하는 조각이 있으면 해당 크기만큼 누적 합산

---

해결 과정 및 코드

핵심 아이디어

1. 2차원 배열에서 특정 값(0 또는 1)으로 연결된 도형(블록 또는 빈칸)을 추출 (BFS를 통해 도형 좌표 리스트 구성)
2. 도형을 좌상단 기준으로 이동시켜 동일 기준으로 비교 가능하게 정규화
   각 도형 좌표를 (최소 row, 최소 col) 기준으로 맞춰서 정렬
3. 퍼즐 조각을 90도씩 회전
   (r, c) → (c, maxRow - r) 변환으로 음수 좌표 방지
4. 정규화된 도형끼리의 좌표 리스트 비교
   크기와 좌표가 정확히 일치해야 매칭

코드

시간 복잡도 : O(N^3)

import java.util.*;

class Solution {
    static int N;
    static final int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
    public int solution(int[][] game_board, int[][] table) {
        N = game_board.length;
        // 1. 빈칸 추출
        List<List<int[]>> emptySpace = extractShapes(game_board, 0);
        // 2. 조각 추출
        List<List<int[]>> puzzlePieces = extractShapes(table, 1);
        
        // 3. 빈칸마다 조각 맞추기
        // 사용한 퍼즐 표시
        boolean [] used = new boolean[puzzlePieces.size()];
        int answer = 0;

        for (List<int []> space : emptySpace) {
            for (int i = 0; i < puzzlePieces.size(); i++) {
                if (used[i]) continue; // 사용한 퍼즐
                
                List<int[]> piece = puzzlePieces.get(i);
                boolean matched = false;
                // 회전
                for (int r = 0; r < 4; r++) {
                    // 빈칸 맞는지 확인
                    if (isSameShape(space, normalize(piece))){
                        answer += space.size();
                        used[i] = true;
                        matched = true;
                        break;
                    }
                    // 90도 회전
                    piece = rotate(piece);
                }

                if (matched) break; // 일치했으면 다른 빈칸 점검
            }
        }
        
        return answer;
    }
    
    // 전체 모양 추출
    private List<List<int[]>> extractShapes(int[][] board, int target) {
        boolean [][] visited = new boolean[N][N];
        List<List<int[]>> shapes = new ArrayList<>();
               
        for (int r = 0; r < N; r++) {
            for (int c=  0; c < N; c++){
                if(!visited[r][c] && board[r][c] == target){
                    shapes.add(normalize(bfs(r, c , board, visited, target)));
                }
            }
        }
        
        return shapes;
    }
    
    // 각 도형 탐색 BFS (각 도형별 좌표값)
    private List<int[]> bfs(int r, int c, int[][] board, boolean[][] visited, int target) {
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        List<int[]> shape = new ArrayList<>();

        visited[r][c] = true;
        queue.offer(new int[]{r, c});
        shape.add(new int[]{r, c});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] d : directions) {
                int nr = cur[0] + d[0];
                int nc = cur[1] + d[1];
                if (isOut(nr, nc) || visited[nr][nc] || board[nr][nc] != target) continue;
                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc});
                shape.add(new int[]{nr, nc});
            }
        }
        return shape;
    }
    
    // 배열 내부 좌표 여부 확인
    private boolean isOut(int r, int c) {
        return r < 0 || r >= N || c < 0 || c >= N;
    }
    
    // 좌상단 기준 정규화
    private List<int[]> normalize(List<int[]> shape) {
        int minR = Integer.MAX_VALUE, minC = Integer.MAX_VALUE;
        // 배열 그림 상 좌상단 좌표 찾기
        for (int [] p : shape) {
            minR = Math.min(p[0], minR);
            minC = Math.min(p[1], minC);
        }
        
        List<int[]> normalized = new ArrayList<>();
        // (2, 0),(2, 1),(3, 0) -> (0, 0),(0, 1),(1, 0) 로 정규화
        for (int[] p : shape) {
            normalized.add(new int[]{p[0] - minR, p[1] - minC});
        }
        normalized.sort(Comparator.<int[]>comparingInt(a -> a[0])
                                  .thenComparingInt(a -> a[1]));
        return normalized;
    }
    
    // 회전 (90도)
    private List<int[]> rotate(List<int[]> shape) {
        int maxR = 0;
        // 회전 시 음수 좌표를 피하고자 배열 그림 상 최하단 탐색
        for (int[] p : shape) {
            maxR = Math.max(maxR, p[0]);
        }

        List<int[]> rotated = new ArrayList<>();
        for (int[] p : shape) {
            int r = p[0], c = p[1];
            // 시계 방향 90도 회전: (x, y) -> (y, -x + maxR) 
            // maxR를 통해 음수 좌표 양수로 보정
            rotated.add(new int[]{c, maxR - r});
        }
        return rotated;
    }

    
    // 도형 좌표 비교 
    boolean isSameShape(List<int[]> a, List<int[]> b) {
        if (a.size() != b.size()) return false;
        for (int i = 0; i < a.size(); i++) {
            if (a.get(i)[0] != b.get(i)[0] || a.get(i)[1] != b.get(i)[1]) {
                return false;
            }
        }
        return true;
	}
}

 

참고 : 2차원 좌표 회전

✅ 1. 회전의 기본 개념

2차원 평면에서 한 점 (x, y)를 기준점(origin) (0, 0)을 중심으로 시계 방향으로 회전하는 경우:

회전 각도	회전 공식 (시계 방향 기준)
90도	(x, y) → (y, -x)
180도	(x, y) → (-x, -y)
270도	(x, y) → (-y, x)

---

✅ 2. 자바 배열 좌표계의 특수성

자바의 2차원 배열에서는 (x, y)가 아니라 보통 (행, 열) = (i, j)로 나타내며, 그림 상:

• x: 행 번호 (아래로 증가) :  수직 방향
• y: 열 번호 (오른쪽으로 증가) : 수평 방향

---

✅ 3. 회전 후 음수 방지 처리

기본 회전 공식은 -x, -y가 들어가서 회전 후 좌표에 음수가 생길 수 있다.

하지만 자바 배열에서는 음수 인덱스가 허용되지 않기 때문에 좌표를 양수로 보정해야 한다.

🔧 해결: 기준점 보정 (정규화 또는 maxX 사용)

• 도형을 좌상단 (0,0) 기준으로 **정규화(normalize)**하고,
• 회전 후 x축을 뒤집을 때는 -x 대신 maxX - x로 바꿔서 음수를 방지한다. (즉 +maxX 만큼 밀기)

---

✅ 5. normalize (정규화) 함수도 꼭 함께 사용

회전 후 좌표가 흩어지기 때문에 반드시 다시 좌상단 (0,0) 기준으로 맞춰야 한다.

List<int[]> normalize(List<int[]> shape) {
    int minX = Integer.MAX_VALUE;
    int minY = Integer.MAX_VALUE;
    for (int[] p : shape) {
        minX = Math.min(minX, p[0]);
        minY = Math.min(minY, p[1]);
    }

    List<int[]> norm = new ArrayList<>();
    for (int[] p : shape) {
        norm.add(new int[]{p[0] - minX, p[1] - minY});
    }

    norm.sort(Comparator.comparingInt((int[] a) -> a[0])
                        .thenComparingInt(a -> a[1]));
    return norm;
}