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

전종원·2024년 8월 26일
99클럽TIL개발자취업코딩테스트준비항해99
0

오늘의 학습 키워드

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시간

profile
전종원
이전 포스트

99클럽 코테 스터디 34일차 TIL / [프로그래머스] 여행경로

다음 포스트

99클럽 코테 스터디 36일차 TIL / [백준] 도미노

0개의 댓글