99클럽 코테 스터디 35일차 TIL / [프로그래머스] 퍼즐 조각 채우기

전종원·2024년 8월 26일
0
post-custom-banner

오늘의 학습 키워드


BFS

문제


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

  • 플랫폼: 프로그래머스
  • 문제명: 퍼즐 조각 채우기
  • 난이도: Lv3

풀이


import java.util.*;

class Solution {
    
    static int answer = 0;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    
    public int solution(int[][] game_board, int[][] table) {    
        for (int i = 0; i < 4; i++) {
            List<Block> blocksOfTable = saveBlocks(table);
            startGame(game_board, table, blocksOfTable);
            rotateTable(table);
        }
        
        return answer;
    }
    
    public List<Block> saveBlocks(int[][] table) {
        int length = table.length;
        boolean[][] visited = new boolean[length][length];
        List<Block> blocks = new ArrayList<>();

        for(int x=0; x<length; x++) {
            for(int y=0; y<length; y++) {
                if(table[x][y] != 0 && !visited[x][y]) {
                    blocks.add(readBlock(x, y, visited, table, 0));
                }
            }
        }

        return blocks;
    }

    private Block readBlock(int x, int y, boolean[][] visited, int[][] table, int readBlockValue) {
        Block block = new Block();
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        visited[x][y] = true;
        block.points.add(new Point(x, y));

        while(!queue.isEmpty()) {
            Point curPoint = queue.poll();
            int cx = curPoint.x;
            int cy = curPoint.y;

            for(int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if(!(nx >=0 && ny >= 0 && nx < table.length && ny < table.length)) {
                    continue;
                }

                if(visited[nx][ny]) {
                    continue;
                }

                if(table[nx][ny] == readBlockValue) {
                    continue;
                }

                queue.offer(new Point(nx, ny));
                visited[nx][ny] = true;
                block.points.add(new Point(nx, ny));
            }
        }

        return block;
    }

    public void startGame(int[][] game_board, int[][] table, List<Block> blocksOfTable) {
        int length = table.length;
        boolean[][] visitedGameBoard = new boolean[length][length];

        for(int x=0; x<length; x++) {
            for(int y=0; y<length; y++) {
                if(game_board[x][y] == 0 && !visitedGameBoard[x][y]) {
                    Block emptyBlock = readBlock(x, y, visitedGameBoard, game_board, 1);
                    fillInIfFit(emptyBlock, blocksOfTable, game_board, table);
                }
            }
        }
    }

    public void fillInIfFit(Block emptyBlock, List<Block> blocksOfTable, int[][] game_board, int[][] table) {
        List<Block> blocks = new ArrayList<>(blocksOfTable);

        // 시작점 동일하게 변경
        Point startPoint = emptyBlock.points.get(0);

        for(int blockNum=0; blockNum<blocks.size(); blockNum++) {
            Block block = blocks.get(blockNum);
            int x = startPoint.x - block.points.get(0).x;
            int y = startPoint.y - block.points.get(0).y;
            boolean isFitBlock = true;

            if (block.points.size() != emptyBlock.points.size()) {
                continue;
            }

            for(int i=1; i<block.points.size(); i++) {
                Point point = block.points.get(i);
                Point EmptyBlockPoint = emptyBlock.points.get(i);

                if(point.x + x != EmptyBlockPoint.x || point.y + y != EmptyBlockPoint.y) {
                    isFitBlock = false;
                    break;
                }
            }

            if(isFitBlock) {
                removeBlockFromTable(table, blocksOfTable, blockNum);
                fillBlockFromGameBoard(game_board, emptyBlock);
                break;
            }
        }
    }

    public void removeBlockFromTable(int[][] table, List<Block> blocksOfTable, int blockNum) {
        Block block = blocksOfTable.get(blockNum);

        for(Point point : block.points) {
            table[point.x][point.y] = 0;
        }

        blocksOfTable.remove(blockNum);
    }

    public void fillBlockFromGameBoard(int[][] game_board, Block emptyBlock) {
        for(Point point : emptyBlock.points) {
            game_board[point.x][point.y] = 1;
            answer++;
        }
    }

    public void rotateTable(int[][] table) {
        int length = table.length;
        int[][] copyTable = new int[length][length];

        for (int x = 0; x < length; x++) {
            copyTable[x] = Arrays.copyOf(table[x], table.length);
        }

        for(int x=0; x<length; x++) {
            for(int y=0; y<length; y++) {
                table[y][length - 1 - x] = copyTable[x][y];
            }
        }
    }

    static class Point {
        int x;
        int y;

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

    static class Block {
        List<Point> points = new ArrayList<>();
    }
}

접근

  • 큰 흐름은 다음과 같습니다.
    1. 테이블에 위치한 블록 탐색 후 저장
    2. 게임 보드에 딱 맞게 넣을 수 있는 위치가 존재하는 지 확인 후 저장
    3. 테이블 회전
    4. 1-3번 과정 반복
  1. 테이블에 위치한 블록 탐색 후 저장

    public List<Block> saveBlocks(int[][] table) {
        int length = table.length;
        boolean[][] visited = new boolean[length][length];
        List<Block> blocks = new ArrayList<>();
    
        for(int x=0; x<length; x++) {
            for(int y=0; y<length; y++) {
                if(table[x][y] != 0 && !visited[x][y]) {
                    blocks.add(readBlock(x, y, visited, table, 0));
                }
            }
        }
    
        return blocks;
    }
    
    private Block readBlock(int x, int y, boolean[][] visited, int[][] table, int readBlockValue) {
        Block block = new Block();
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        visited[x][y] = true;
        block.points.add(new Point(x, y));
    
        while(!queue.isEmpty()) {
            Point curPoint = queue.poll();
            int cx = curPoint.x;
            int cy = curPoint.y;
    
            for(int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
    
                if(!(nx >=0 && ny >= 0 && nx < table.length && ny < table.length)) {
                    continue;
                }
    
                if(visited[nx][ny]) {
                    continue;
                }
    
                if(table[nx][ny] == readBlockValue) {
                    continue;
                }
    
                queue.offer(new Point(nx, ny));
                visited[nx][ny] = true;
                block.points.add(new Point(nx, ny));
            }
        }
    
        return block;
    }
    • BFS를 통해 테이블에 위치한 블록을 탐색하고, 그 좌표들을 저장했습니다.
  2. 게임 보드에 딱 맞게 넣을 수 있는 위치가 존재하는 지 확인 후 저장

    public void fillInIfFit(Block emptyBlock, List<Block> blocksOfTable, int[][] game_board, int[][] table) {
        List<Block> blocks = new ArrayList<>(blocksOfTable);
    
        // 시작점 동일하게 변경
        Point startPoint = emptyBlock.points.get(0);
    
        for(int blockNum=0; blockNum<blocks.size(); blockNum++) {
            Block block = blocks.get(blockNum);
            int x = startPoint.x - block.points.get(0).x;
            int y = startPoint.y - block.points.get(0).y;
            boolean isFitBlock = true;
    
            if (block.points.size() != emptyBlock.points.size()) {
                continue;
            }
    
            for(int i=1; i<block.points.size(); i++) {
                Point point = block.points.get(i);
                Point EmptyBlockPoint = emptyBlock.points.get(i);
    
                if(point.x + x != EmptyBlockPoint.x || point.y + y != EmptyBlockPoint.y) {
                    isFitBlock = false;
                    break;
                }
            }
    
            if(isFitBlock) {
                removeBlockFromTable(table, blocksOfTable, blockNum);
                fillBlockFromGameBoard(game_board, emptyBlock);
                break;
            }
        }
    }
    
    public void removeBlockFromTable(int[][] table, List<Block> blocksOfTable, int blockNum) {
        Block block = blocksOfTable.get(blockNum);
    
        for(Point point : block.points) {
            table[point.x][point.y] = 0;
        }
    
        blocksOfTable.remove(blockNum);
    }
    
    public void fillBlockFromGameBoard(int[][] game_board, Block emptyBlock) {
        for(Point point : emptyBlock.points) {
            game_board[point.x][point.y] = 1;
            answer++;
        }
    }
    • 1번 과정에서 저장한 블록의 좌표들을 토대로, 게임 보드에 넣을 수 있는지 확인합니다.
    • 이때, 게임 보드에 빈 공간에 대한 BFS 탐색이 이루어지고 좌표에 대한 정보는 emptyBlock이라는 변수에 저장됩니다.
    • BFS는 동일 로직을 따르기 때문에, emptyBlock과 테이블에 위치한 블록들의 시작 좌표만 맞춘다면 모양이 일치하는지 비교할 수 있습니다.
    • 만약 게임 보드에 채울 수 있다면, 그 위치를 1 값으로 변경하고(fillBlockFromGameBoard) 테이블 배열에는 0 값으로 변경(removeBlockFromTable)합니다.
  3. 테이블 회전

    public void rotateTable(int[][] table) {
        int length = table.length;
        int[][] copyTable = new int[length][length];
    
        for (int x = 0; x < length; x++) {
            copyTable[x] = Arrays.copyOf(table[x], table.length);
        }
    
        for(int x=0; x<length; x++) {
            for(int y=0; y<length; y++) {
                table[y][length - 1 - x] = copyTable[x][y];
            }
        }
    }
    • 블록을 회전할 수 있다는 조건이 있으므로, 실제로 테이블 배열을 회전시키며 비교를 진행했습니다.

소요 시간

3시간

post-custom-banner

0개의 댓글