[프로그래머스] 84021 퍼즐 조각 채우기 ( 위클리 챌린지 3주차 )

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 3주차

2. 접근방법

빡구현인 문제

 

타일을 빈칸에 정확히 들어가게 넣어야 하는데 회전해서 넣는 것이 가능하다.

 

어떤 고려해야할 조건도 없고 그저 타일을 돌려보다가 빈칸과 딱 맞으면 집어넣으면 되는 간단하지만 구현하긴 힘든 문제이다.

 

그래도 조금이라도 편하게 풀려고 몇가지 방법들을 사용해봤다.

 

먼저 game_board와 table을 하나의 함수로 처리하기 위해 game_board의 빈칸과 table의 타일칸이 동일한 의미를 가지도록 game_board의 0과 1을 바꾸어 주었다.

 

그리고 각 타일과 빈칸이 같은지 비교하기 쉽도록 각 타일과 빈칸을 String으로 변환하여 Hash로 사용하기 용이하게 바꾸었다.

---

풀이과정은

 

1. 먼저 game_board 와 table을 하나의 함수로 처리하기 위해 game_board의 0과 1을 바꾸어 빈칸을 채워넣었다.

2. 그 다음 game_board에서 빈칸을 만나면 bfs를 돌면서 그 빈칸 모양을 하나의 String으로 변환해주는 작업을 하였다.

2-1. 찾은 모형에 사각형을 씌우고 빈칸인 부분에 1을 채워 넣고 나머지 부분은 0을 채워넣어주었고 줄바뀜때에 n을 넣어줬다.

위 그림의 경우 "110n010n011n"으로 변환된다.

 

3. 각 모형들이 String으로 변환되었기 때문에 이제 hash를 이용해서 저장이 가능하게 되었다.

4. 모형의 String을 key로, 모형의 갯수와 모형의 크기를 Point에 저장하여 value로 HashMap에 저장한다.

5. 이제 table에서 2번에서 한 것처럼 bfs를 돌리고 각 모형을 String 변환한다.

6. HashMap에서 해당하는 값이 있다면 모형의 크기를 answer에 + 하고,모형의 갯수는 - 한다.

7. 모형의 갯수가 0이 되면 HashMap에서 제거, 사용한 타일은 table에서 0으로 채워넣어 삭제한다.

8. 모든 타일을 확인하였으면 table을 회전하고 5번부터 다시 반복한다.

9. 회전을 총 4번하면 종료

 

3. 자바 코드

import java.awt.*;
import java.util.*;

public class P84021퍼즐조각채우기 {

    HashMap<String, Point> blockStore = new HashMap<>();
    int cnt = 0;
    ArrayList<Point> block;

    public int solution(int[][] game_board, int[][] table) {
        int answer = 0;
        for (int i = 0; i < game_board.length; i++)
            for (int j = 0; j < game_board.length; j++)
                game_board[i][j] = game_board[i][j] == 0 ? 1 : 0;
        for (int i = 0; i < game_board.length; i++)
            for (int j = 0; j < game_board.length; j++)
                if (game_board[i][j] == 1) {
                    String blockString = bfs(game_board, i, j);
                    Point bp = blockStore.getOrDefault(blockString, new Point(0, cnt));
                    bp.x++;
                    blockStore.put(blockString, bp);
                }
        for (int r = 0; r < 4; r++) {
            table = rotate(table);
            int[][] temptable = new int[table.length][table.length];
            for (int d = 0; d < table.length; d++)
                temptable[d] = table[d].clone();
            for (int i = 0; i < temptable.length; i++)
                for (int j = 0; j < temptable.length; j++)
                    if (temptable[i][j] == 1) {
                        String blockString = bfs(temptable, i, j);
                        if (blockStore.containsKey(blockString)) {
                            for (Point bp : block)
                                table[bp.x][bp.y] = 0;
                            Point p = blockStore.get(blockString);
                            answer += p.y;
                            if (--p.x == 0)
                                blockStore.remove(blockString);
                            else
                                blockStore.put(blockString, p);
                        }
                    }
        }
        return answer;
    }

    int[][] rotate(int[][] board) {
        int[][] newboard = new int[board.length][board.length];
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board.length; j++)
                newboard[j][board.length - i - 1] = board[i][j];
        return newboard;
    }

    String bfs(int[][] board, int x, int y) {
        int dr[] = new int[]{1, -1, 0, 0};
        int dc[] = new int[]{0, 0, 1, -1};
        int minX = 987654321;
        int minY = 987654321;
        int maxX = 0;
        int maxY = 0;
        Queue<Point> que = new LinkedList<>();
        block = new ArrayList<>();
        que.add(new Point(x, y));
        board[x][y] = 0;
        cnt = 0;

        while (!que.isEmpty()) {
            Point now = que.poll();
            cnt++;
            minX = Math.min(now.x, minX);
            minY = Math.min(now.y, minY);
            maxX = Math.max(now.x, maxX);
            maxY = Math.max(now.y, maxY);
            block.add(new Point(now.x, now.y));
            for (int i = 0; i < 4; i++) {
                int nowx = now.x + dr[i];
                int nowy = now.y + dc[i];
                if (nowx < 0 || nowy < 0 || nowx >= board.length || nowy >= board.length)
                    continue;
                if (board[nowx][nowy] == 0)
                    continue;
                board[nowx][nowy] = 0;
                que.add(new Point(nowx, nowy));
            }
        }
        return makeString(minX, minY, maxX, maxY, block);

    }

    String makeString(int minX, int minY, int maxX, int maxY, ArrayList<Point> block) {
        int[][] blockArr = new int[maxX - minX + 1][maxY - minY + 1];
        for (Point p : block)
            blockArr[p.x - minX][p.y - minY] = 1;
        String blockString = "";
        for (int i = 0; i < blockArr.length; i++) {
            for (int j = 0; j < blockArr[0].length; j++)
                blockString += blockArr[i][j];
            blockString += "n";
        }
        return blockString;
    }
}

4. 마치며

문제 자체는 어렵지 않지만 구현하기엔 많은 체력을 요구하는

뭔가 삼성 코테 느낌의 문제였다.