99클럽 코테 스터디 35일차 TIL [DFS, BFS]

 

- 오늘의 학습 키워드 : DFS, BFS, 시뮬레이션

[문제 이름 : 퍼즐 조각 채우기 (프로그래머스, Lv 3)]

문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/84021

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    static class Pair implements Comparable<Pair> {
        int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.x == o.x) {
                return this.y - o.y;
            }
            return this.x - o.x;
        }

        // 같은 객체인지 확인
        public boolean isSame(Pair o) {
            return this.compareTo(o) == 0;
        }
    }

    int n;
    boolean[][] visited;
    List<List<Pair>> boardShapes, puzzlePieces;

    public int solution(int[][] game_board, int[][] table) {
        n = game_board.length;
        visited = new boolean[n][n];
        boardShapes = new ArrayList<>();
        puzzlePieces = new ArrayList<>();

        // 보드에서 빈 공간 모양 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (game_board[i][j] == 0 && !visited[i][j]) {
                    List<Pair> shape = new ArrayList<>();
                    extractShape(game_board, i, j, shape, 0);
                    boardShapes.add(normalizeShape(shape));
                }
            }
        }

        // 방문 배열 초기화
        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]) {
                    List<Pair> piece = new ArrayList<>();
                    extractShape(table, i, j, piece, 1);
                    puzzlePieces.add(normalizeShape(piece));
                }
            }
        }

        // 퍼즐 조각들을 보드의 빈 공간에 채워 넣기
        int totalFilled = 0;
        for (List<Pair> piece : puzzlePieces) {
            boolean piecePlaced = false;
            for (int i = 0; i < boardShapes.size(); i++) {
                if (boardShapes.get(i) == null) continue;
                if (canFit(boardShapes.get(i), piece)) {
                    totalFilled += piece.size();
                    // 해당 보드 모양을 사용했으므로 제거
                    boardShapes.set(i, null); 
                    piecePlaced = true;
                    break;
                }
            }
        }

        return totalFilled;
    }

    // 주어진 위치에서 연결된 모양을 추출
    private void extractShape(int[][] grid, int x, int y, List<Pair> shape, int target) {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            shape.add(p);

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && grid[nx][ny] == target) {
                    visited[nx][ny] = true;
                    queue.add(new Pair(nx, ny));
                }
            }
        }
    }

    // 모양을 (0, 0) 기준으로 정규화
    private List<Pair> normalizeShape(List<Pair> shape) {
        Collections.sort(shape);
        int minX = shape.get(0).x;
        int minY = shape.get(0).y;

        List<Pair> normalized = new ArrayList<>();
        for (Pair p : shape) {
            normalized.add(new Pair(p.x - minX, p.y - minY));
        }
        return normalized;
    }

    // 주어진 퍼즐 조각이 보드의 빈 공간에 맞출 수 있는지 확인
    private boolean canFit(List<Pair> boardShape, List<Pair> piece) {
        if (boardShape.size() != piece.size()) return false;

        for (int rotation = 0; rotation < 4; rotation++) {
            boolean matches = true;
            for (int i = 0; i < boardShape.size(); i++) {
                if (!boardShape.get(i).isSame(piece.get(i))) {
                    matches = false;
                    break;
                }
            }
            if (matches) return true;
            piece = rotatePiece(piece);
        }
        return false;
    }

    // 퍼즐 조각을 90도 회전
    private List<Pair> rotatePiece(List<Pair> piece) {
        List<Pair> rotated = new ArrayList<>();
        for (Pair p : piece) {
            rotated.add(new Pair(p.y, -p.x));
        }
        return normalizeShape(rotated);
    }
}

 

[풀이 과정]

1. Pair 클래스로 각 좌표를 저장하며, visited 배열은 각 좌표의 방문 여부를 기록하기 위해 사용된다. boardShapes 리스트는 게임 보드에서 빈 공간의 모양들을 저장하고, puzzlePieces는 테이블에서 퍼즐 조각들의 모양을 저장한다.

2. extractShape 메서드로 게임 보드에서 0인 부분(빈 공간)을 찾아 그 모양을 추출한다. BFS를 이용해 모든 좌표를 탐색하고, 추출된 모양은 normalizeShape라는 메서드를 통해 (0,0)을 기준으로 변환된다.

3. normalizeShape 메서드는 추출된 좌표 리스트를 정렬하고, 리스트의 첫 번째 좌표를 기준으로 모든 좌표를 상대적으로 이동시켜 정규화된 좌표 리스트를 만든다.

4. 추출된 퍼즐 조각들을 게임 보드의 빈 공간에 맞춰본다. 이때 canFit 메서드를 사용하여 퍼즐 조각이 보드의 빈 공간에 맞는지 확인한다. 이때, 퍼즐 조각은 최대 4번까지 90도 회전하며 비교한다.

5. 퍼즐 조각이 빈 공간에 맞으면, 해당 공간을 채웠다고 보고 총 채운 면적을 업데이트 한다. 이후, 이 면적을 리턴한다.

 

코드가 잘 떠오르지 않아 다른 사람의 풀이를 참고하여 문제를 풀이하고, 코드를 리팩토링했다.

풀이 시간 : 3시간