99클럽 코테 스터디 11일차 TIL - 그래프 탐색(DFS/BFS)

항해99 코테 스터디 11일차 문제인 프로그래머스의 '퍼즐 조각 채우기'는 테이블 위의 퍼즐 조각으로 보드의 빈칸에 최대한 채우는 문제다. 난이도는 레벨3이며 DFS 및 BFS를 통해 해결할 수 있다.

 

오늘의 문제 - 퍼즐 조각 채우기 문제 정보

문제 키워드

- DFS/BFS

난이도

- Level 3

 

문제 요약

• 퍼즐 조각들이 놓여진 테이블 배열과, 빈칸들이 뚫려있는 보드판 배열이 주어진다.
• 퍼즐로 빈칸을 채우는데, 채울 때 모양과 크기가 딱 맞는 빈칸만 채울 수 있다. (퍼즐 회전 가능)
• 최대로 채웠을 때 재워지는 빈칸의 칸수를 구하라.

 

문제 풀이 과정  

• 먼저 퍼즐 조각과 빈칸 조각들의 개수와 크기를 구하였다.
  • 이를 구하기 위해, BFS를 사용하여 어떤 좌표가 포함된 블록의 크기를 구하는 메서드를 구현했다.
• 각 퍼즐 조각에 대해, 크기가 같은 빈칸과 모양을 대조해본다.
  • 퍼즐을 회전시키는 것이 가능하므로, 높이와 너비를 이용해 회전 각도를 결정한다.
  • 퍼즐과 빈칸의 모양이 같다면 빈칸을 채우고, 빈칸 리스트에서 빈칸을 삭제한다.
• 모든 채워진 빈칸의 크기를 합한 것이 정답이 된다.

코드

import java.util.*;

class Solution {
    
    private final int[][] drdc = {{0, 0, 1, -1}, {1, -1, 0, 0}};

    public int solution(int[][] game_board, int[][] table) {
        int answer = 0;
        int N = game_board.length;

        // 보드 빈칸들 구하기
        Map<Integer, List<Block>> blanks = new HashMap<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (game_board[r][c] == 0) {
                    Block blank = getBlock(game_board, r, c, 0);
                    blanks.putIfAbsent(blank.cnt, new ArrayList<>());
                    blanks.get(blank.cnt).add(blank);
                }
            }
        }
        
        // 블록 조각들 구하기
        List<Block> blocks = new ArrayList<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (table[r][c] == 1) {
                    blocks.add(getBlock(table, r, c, 1));
                }
            }
        }

        // 각 블록 조각과 사이즈가 같은 빈칸을 맞춰보기
        for (Block block : blocks) {
            Block matched = null;
            if (blanks.containsKey(block.cnt)){
                for (Block blank : blanks.get(block.cnt)) {
                    if (isSameBlock(game_board, table, blank, block)) {
                        matched = blank;
                        break;
                    }
                }
            }
            
            // 빈칸에 블록이 맞으면 정답 카운트 추가 및 빈칸 삭제
            if (matched != null) {
                answer += block.cnt;
                blanks.get(block.cnt).remove(matched);
            }
        }


        return answer;
    }

    // 보드에서 (r,c)칸을 포함하는 블록을 구하는 메서드 (BFS 이용)
    private Block getBlock(int[][] board, int r, int c, int flag) {
        int cnt = 0;
        int tlR = r, tlC = c, brR = r, brC = c;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r, c});
        board[r][c] = 2;

        while (!q.isEmpty()) {
            int[] here = q.poll();
            int hereR = here[0], hereC = here[1];
            
            // 블록의 칸 개수, 좌측상단, 우측하단 좌표도 함께 구함
            cnt++;
            tlR = Integer.min(tlR, hereR);
            tlC = Integer.min(tlC, hereC);
            brR = Integer.max(brR, hereR);
            brC = Integer.max(brC, hereC);

            // 현재 좌표에서 인접한, 블록에 포함되는 공간을 방문
            for (int d = 0; d < 4; d++) {
                int nextR = hereR + drdc[0][d];
                int nextC = hereC + drdc[1][d];

                if (nextR >= 0 && nextR < board.length
                        && nextC >= 0 && nextC < board.length
                        && board[nextR][nextC] == flag) {
                    q.add(new int[]{nextR, nextC});
                    board[nextR][nextC] = 2;
                }
            }
        }

        return new Block(r, c, tlR, tlC, brR, brC, cnt);
    }

    // 두 보드의 각 블록이 같은 모양을 가지고 있는지 확인하는 메서드
    private boolean isSameBlock(int[][] boardA, int[][] boardB, Block a, Block b) {
        int aH = a.getHeight(), aW = a.getWidth();
        int bH = b.getHeight(), bW = b.getWidth();

        // 블록 크기에 따라 회전 방향을 결정
        // 블록 크기가 다르면 바로 false 반환
        int[] rotates;
        if (aH == bH && aW == bW) {
            if (aH == aW) {
                rotates = new int[]{0, 1, 2, 3};
            } else {
                rotates = new int[]{0, 2};
            }
        } else if (aH == bW && aW == bH) {
            rotates = new int[]{1, 3};
        } else {
            return false;
        }

        boolean canMatch = false;

        // B블록을 회전하면서 A블록과 동일한 모양인지 확인
        for (int i : rotates) {
            boolean isMatched = true;
            for (int r = 0; r < aH; r++) {
                for (int c = 0; c < aW; c++) {
                    int aR = a.tlR + r, aC = a.tlC + c;
                    int bR = b.tlR + getRotate(r, c, bH, bW, i)[0];
                    int bC = b.tlC + getRotate(r, c, bH, bW, i)[1];
                    if ((boardA[aR][aC] == 2 && boardB[bR][bC] != 2)
                            || (boardB[bR][bC] == 2 && boardA[aR][aC] != 2)) {
                        isMatched = false;
                        break;
                    }
                }
                if (!isMatched) break;
            }
            if (isMatched) {
                canMatch = true;
                break;
            }
        }

        return canMatch;
    }

    // 0, 90, 180, 270도 회전했을 때 좌표를 구하는 메서드
    private int[] getRotate(int r, int c, int H, int W, int d) {
        switch (d) {
            case 0:
                return new int[]{r, c};
            case 1:
                return new int[]{H - c - 1, r};
            case 2:
                return new int[]{H - r - 1, W - c - 1};
            case 3:
                return new int[]{c, W - r - 1};
        }
        return new int[]{r, c};
    }

    class Block {
        int r;
        int c;
        int tlR;
        int tlC;
        int brR;
        int brC;
        int cnt;

        public Block(int r, int c, int tlR, int tlC, int brR, int brC, int cnt) {
            this.r = r;
            this.c = c;
            this.tlR = tlR;
            this.tlC = tlC;
            this.brR = brR;
            this.brC = brC;
            this.cnt = cnt;
        }

        public int getWidth() {
            return brC - tlC + 1;
        }

        public int getHeight() {
            return brR - tlR + 1;
        }
    }
}

• 시간복잡도: O(N^2) → N: 보드 넓이(=높이)
• 공간복잡도: O(N^2)

 

오늘의 학습 회고

• 전형적인 그래프 탐색 문제이고, 푸는 방법도 다 아는데 구현이 너무 오래걸렸다.
• 특히 회전 후 좌표를 구하는 부분이 헷갈려서 시간을 많이 잡아먹었다.
• 문제를 많이 풀면서 연습을 많이 해서 구현 시간을 줄여보자!