[Algorithm: DFS] 프로그래머스 <퍼즐 조각 채우기>

DFS 구현 Java Programmers Lv.3

문제

https://school.programmers.co.kr/learn/courses/30/lessons/84021?language=java

프로그래머스

 

 

---

 

문제 설명

game_board의 빈칸(0)에 table의 퍼즐 조각(1)을 맞춰 넣는 문제다. 조각은 회전이 가능하고, 빈칸과 조각의 모양이 정확히 일치할 때만 채울 수 있다. 최대한 많은 칸을 채웠을 때의 총 칸 수를 구한다.

핵심 규칙: 새로 채워 넣은 조각과 인접한 칸이 비어있으면 안 된다.
즉, 빈칸의 모양과 조각의 모양이 완전히 일치해야 채울 수 있다.

 

---

 

전체 풀이 전략

이 문제는 구현 단계가 많다. 전체 흐름을 먼저 파악하면 각 단계를 이해하기 쉽다.

① DFS
빈칸 추출

→

② DFS
조각 추출

→

③ 정규화
(위치 제거)

→

④ 회전
(0°~270°)

→

⑤ 모양
비교

→

⑥ 정답
누적

 

① ② DFS로 덩어리 추출 

연결된 칸들을 하나의 덩어리로 묶는 작업이다. game_board에서 0(빈칸) 덩어리를, table에서 1(조각) 덩어리를 각각 DFS로 추출한다.

game_board (0이 빈칸)

1

1

0

0

1

1

0

0

1

1

1

0

1

0

0

0

0

1

1

1

0

1

1

1

1

🔵 0 덩어리 1: (0,2)(0,3)(1,2)(1,3)... 추출
🔵 0 덩어리 2: (1,1)(2,1)... 추출
🔵 각 덩어리 → 좌표 리스트로 저장

dfs()에 target 파라미터를 두어 0 탐색과 1 탐색을 같은 함수로 처리했다.
game_board[nx][ny] == target 조건으로 빈칸/조각을 구분한다.

void dfs(boolean[][] visited, int x, int y,
         int[][] board, List<int[]> shape, int target) {
    visited[x][y] = true;
    shape.add(new int[]{x, y});

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 || ny < 0 || nx >= board.length || ny >= board.length) continue;
        if (!visited[nx][ny] && board[nx][ny] == target) {
            dfs(visited, nx, ny, board, shape, target);
        }
    }
}

  

 

③ 정규화: 위치를 제거하고 모양만 남기기

DFS로 추출한 좌표는 그리드에서의 절대 위치를 포함한다. 그러면 같은 모양이어도 위치가 달라 비교가 불가능하다. 정규화는 가장 작은 x, y를 0으로 맞춰 순수한 모양만 남기는 과정이다.

정규화 예시 — L자 모양 조각

DFS로 추출된 원래 좌표 (절대 위치 포함)

(2,3) (3,3) (4,3) (4,4)

minX=2, minY=3 → 전부 빼기

(2,3) → (0,0)    (3,3) → (1,0)    (4,3) → (2,0)    (4,4) → (2,1)

정규화 전 (절대 위치)

 

 

 

 

 

 

 

 

 

 

 

 

 

●

 

 

 

 

●

 

 

 

 

●

●

→

정규화 후 (원점 기준)

●

 

 

●

 

 

●

●

 

List<int[]> normalize(List<int[]> shape) {
    int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
    for (int[] p : shape) {
        minX = Math.min(minX, p[0]);
        minY = Math.min(minY, p[1]);
    }
    List<int[]> result = new ArrayList<>();
    for (int[] p : shape) {
        result.add(new int[]{p[0] - minX, p[1] - minY});
    }
    // 정렬: 비교를 위해 항상 같은 순서로
    result.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
    return result;
}

정규화 후 반드시 정렬해야 한다.
DFS 탐색 순서에 따라 좌표가 다른 순서로 쌓일 수 있기 때문에, 정렬 없이 비교하면 같은 모양인데도 다르다고 판단할 수 있다.

 

 

④ 회전: 90도씩 4번 시도

조각은 회전이 가능하므로 0°, 90°, 180°, 270° 총 4가지 방향을 모두 시도해야 한다. 90도 회전의 좌표 변환 공식은 다음과 같다.

// 90도 시계 방향 회전 공식 (x, y) → (y, -x) // 회전 후 음수 좌표가 생기므로 normalize로 원점 정렬 rotated → normalize(rotated)

L자 조각 90도씩 회전

0° (원본)

●

 

●

 

●

●

(0,0)(1,0)(2,0)(2,1)

↻

90°

●

●

●

●

 

 

(0,0)(0,1)(0,2)(1,0)

↻

180°

●

●

 

●

 

●

(0,0)(0,1)(1,1)(2,1)

↻

 

270°

 

 

●

●

●

●

(0,2)(1,0)(1,1)(1,2)

List<int[]> rotate(List<int[]> shape) {
    List<int[]> rotated = new ArrayList<>();
    for (int[] p : shape) {
        rotated.add(new int[]{p[1], -p[0]});  // (x,y) → (y,-x)
    }
    return normalize(rotated);  // 음수 좌표 제거
}

 

 

⑤ 모양 비교: isSame()

정규화 + 정렬된 좌표 리스트를 인덱스별로 비교한다. 리스트 크기가 같고 모든 좌표가 일치하면 같은 모양이다.

빈칸과 조각 비교 예시

빈칸 정규화 결과

(0,0) (1,0) (2,0) (2,1)

조각 90° 회전 후 정규화 결과

(0,0) (1,0) (2,0) (2,1)

모든 좌표 일치 → 매칭 성공!

boolean isSame(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]) return false;
        if (a.get(i)[1] != b.get(i)[1]) return false;
    }
    return true;
}

비교 전에 크기(칸 수)부터 먼저 확인한다. 크기가 다르면 아무리 회전해도 일치할 수 없어서 불필요한 회전 4번을 건너뛸 수 있다.

 

 

⑥ 매칭 루프: 빈칸마다 모든 조각 시도

추출한 빈칸 목록과 조각 목록을 2중 루프로 순회하며, 각 조각을 4방향 회전하면서 빈칸과 비교한다.

boolean[] used = new boolean[pieces.size()];

for (List<int[]> blank : blanks) {
    for (int i = 0; i < pieces.size(); i++) {
        if (used[i]) continue;                  // 이미 사용한 조각 스킵
        if (blank.size() != pieces.get(i).size()) continue; // 크기 다르면 스킵

        List<int[]> piece = pieces.get(i);
        for (int r = 0; r < 4; r++) {            // 4방향 회전 시도
            if (isSame(blank, piece)) {
                answer += blank.size();
                used[i] = true;
                break;
            }
            piece = rotate(piece);
        }
        if (used[i]) break;                      // 매칭됐으면 다음 빈칸으로
    }
}

used[] 배열의 역할: 조각은 한 번만 사용할 수 있다.
한 번 빈칸에 매칭된 조각은 used[i]=true로 표시해서 다른 빈칸에 재사용되지 않도록 막는다.

 

 

---

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int[][] game_board, int[][] table) {
        int answer = 0;
        List<List<int[]>> blanks = new ArrayList<>();
        List<List<int[]>> pieces = new ArrayList<>();
        int n = game_board.length;
        boolean[][] visitedBoard = new boolean[n][n];
        boolean[][] visitedTable = new boolean[n][n];

        // 빈칸 추출 (0 덩어리)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (game_board[i][j] == 0 && !visitedBoard[i][j]) {
                    List<int[]> shape = new ArrayList<>();
                    dfs(visitedBoard, i, j, game_board, shape, 0);
                    blanks.add(normalize(shape));
                }
            }
        }

        // 조각 추출 (1 덩어리)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (table[i][j] == 1 && !visitedTable[i][j]) {
                    List<int[]> shape = new ArrayList<>();
                    dfs(visitedTable, i, j, table, shape, 1);
                    pieces.add(normalize(shape));
                }
            }
        }

        // 매칭
        boolean[] used = new boolean[pieces.size()];
        for (List<int[]> blank : blanks) {
            for (int i = 0; i < pieces.size(); i++) {
                if (used[i]) continue;
                if (blank.size() != pieces.get(i).size()) continue;
                List<int[]> piece = pieces.get(i);
                for (int r = 0; r < 4; r++) {
                    if (isSame(blank, piece)) {
                        answer += blank.size();
                        used[i] = true;
                        break;
                    }
                    piece = rotate(piece);
                }
                if (used[i]) break;
            }
        }
        return answer;
    }

    void dfs(boolean[][] visited, int x, int y,
             int[][] board, List<int[]> shape, int target) {
        visited[x][y] = true;
        shape.add(new int[]{x, y});
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= board.length || ny >= board.length) continue;
            if (!visited[nx][ny] && board[nx][ny] == target) dfs(visited, nx, ny, board, shape, target);
        }
    }

    List<int[]> normalize(List<int[]> shape) {
        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
        for (int[] p : shape) { minX = Math.min(minX, p[0]); minY = Math.min(minY, p[1]); }
        List<int[]> result = new ArrayList<>();
        for (int[] p : shape) result.add(new int[]{p[0] - minX, p[1] - minY});
        result.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        return result;
    }

    List<int[]> rotate(List<int[]> shape) {
        List<int[]> rotated = new ArrayList<>();
        for (int[] p : shape) rotated.add(new int[]{p[1], -p[0]});
        return normalize(rotated);
    }

    boolean isSame(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;
    }
}

 

 

 

---

 

정리

DFS로 덩어리 추출

빈칸(0)과 조각(1)을 같은 함수로 처리. target 파라미터로 구분해 코드 중복 제거.

정규화

절대 위치 → 상대 위치 변환. minX, minY를 빼서 원점 기준 모양만 남긴다. 정렬 필수.

회전 공식

(x, y) → (y, -x). 회전 후 음수 좌표가 생기므로 normalize를 다시 적용한다.

크기 먼저 비교

blank.size() ≠ piece.size()면 즉시 스킵. 4번의 회전 비교를 건너뛰는 최적화.

이 문제의 핵심은 "모양을 어떻게 비교할 것인가"다.
위치 정보를 제거하는 정규화와, 회전 후 다시 정규화하는 패턴은
격자에서 모양을 비교하는 문제 전반에 재사용할 수 있는 중요한 기법이다.

 

 

 

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.