[Programmers] 퍼즐 조각 채우기

난이도 : Level 3

문제링크

• 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채워야 한다
• 보드의 빈공간과 조각은 딱 맞아떨어져야 한다
• 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 리턴하라
  • 조각을 회전시킬 수 있음
  • 조각끼리는 서로 인접할 수 없다

 

해설

• game_board에 있는 빈칸들과 table에 있는 퍼즐들을 각각 List에 담습니다
  • 각각 인접한 빈칸과 퍼즐을 (0, 0)에서 시작하는 리사이징 2차원 배열을 생성하고 list에 담습니다.
    
  • 빈칸과 퍼즐을 비교하기 위함입니다.
• 빈칸에 현재 가지고 있는 퍼즐들을 하나씩 맞춰보면서 딱 맞으면 퍼즐의 갯수만큼 누적합을 계산합니다.
  • 퍼즐에 빈칸이 맞지 않으면 시계방향으로 90도 회전해 봅니다
  • 회전해도 맞지 않다면 해당 퍼즐은 빈칸에 맞지 않는 퍼즐입니다
• 빈칸별 모든 퍼즐들을 맞출때까지 반복합니다.
• 누적되어있는 퍼즐의 갯수를 리턴합니다.

 

1. 빈칸들과 퍼즐들의 조각 모으기

public List<int[][]> seek(int[][] table, int val) {
    int size = table.length;
    List<int[][]> itemList = new ArrayList<>();

    for (int r = 0; r < size; r++) {
        for (int c = 0; c < size; c++) {
            if (table[r][c] == val) {
                int[] shape = new int[] {r, r, c, c};
                int[][] item = new int[size][size];
                item[r][c] = 1;
                Stack<int[]> stack = new Stack<>();
                stack.push(new int[] {r, c});

                while (!stack.isEmpty()) {
                    int[] p = stack.pop();
                    int cr = p[0], cc = p[1];

                    shape = new int[] {
                        Math.max(shape[0], cr),
                        Math.min(shape[1], cr),
                        Math.max(shape[2], cc),
                        Math.min(shape[3], cc),
                    };     

                    for (int[] dir : directions) {
                        int nr = cr + dir[0], nc = cc + dir[1];
                        if (nr >= 0 && nr < size && nc >= 0 && nc < size && table[nr][nc] == val) {
                            item[nr][nc] = 1;
                            table[nr][nc] = val+1;
                            stack.push(new int[]{nr, nc});
                        }
                    }                                                
                }

                int[][] resizedItem = new int[shape[0]-shape[1]+1][shape[2]-shape[3]+1];
                for (int i = shape[1], y = 0; i <= shape[0]; i++, y++) {
                    for (int j = shape[3], x = 0; j <= shape[2]; j++, x++) {
                        resizedItem[y][x] = item[i][j];
                    }
                }

                itemList.add(resizedItem);
            }
        }
    }

    return itemList;
}

• DFS 탐색으로 찾고자 하는 값의 인접한 좌표들을 item 배열에 표시합니다.
• 좌표들이 표시된 item 배열을 사용하여 (0, 0)에서 시작하는 리사이징 2차원 배열을 생성하고 list에 담습니다.
  • 리사이징 배열의 사이즈를 잡기 위해 shape 배열을 선언합니다.
  • max_row, min_row, max_col, min_col 좌표값들을 저장합니다.

 

2. 빈칸과 퍼즐의 매칭여부 확인

private int match(int[][] blank, int[][] puzzle) {
    int[] blankShape = new int[] {blank.length, blank[0].length};
    int[] puzzleShape = new int[] {puzzle.length, puzzle[0].length};

    Arrays.sort(blankShape);
    Arrays.sort(puzzleShape);

    if (!Arrays.equals(blankShape, puzzleShape)) return 0;

    for (int i = 0; i < 4; i++) {
        if (isSame(blank, puzzle)) {
            return Arrays.stream(puzzle).mapToInt(row -> Arrays.stream(row).sum()).sum();
        }
        puzzle = rotate90(puzzle);
    }

    return 0;
}

• 빈칸과 퍼즐 배열 혹은 회전된 버전의 배열의 폭, 높이가 일치하지 않다면, 일치하지 않은 배열이다.
• 빈칸과 퍼즐이 일치한지 확인한다
  • 일치하지 않는다면 퍼즐을 회전하여 일치여부를 확인한다
  • 3번까지 회전해봅니다.
• 빈칸과 퍼즐이 일치한다면, 퍼즐의 칸수를 리턴한다.
• 빈칸과 퍼즐이 일치하지 않는다면, 0을 리턴한다.

 

3. 빈칸과 퍼즐의 일치여부 확인

private boolean isSame(int[][] blank, int[][] puzzle) {
    if (blank.length != puzzle.length || blank[0].length != puzzle[0].length) return false;
    for (int r = 0; r < blank.length; r++) {
        for (int c = 0; c < blank[0].length; c++) {
            if (blank[r][c] != puzzle[r][c]) return false;
        }
    }

    return true;
}

• 두 배열의 폭과 너비가 일치하는지 체크합니다.
  • 일치하지 않다면 false를 리턴합니다.
  • 일차한다면 모든점들을 순회하며 값이 동등한지 확인합니다.
    • 한점이라도 동등하지 않다면 false를 리턴합니다.
    • 모든 점이 동등하다면 true를 리턴합니다.

 

4. 90도 회전된 퍼즐 반환하기

private int[][] rotate90(int[][] item) {
    int rows = item.length, cols = item[0].length;
    int[][] rotatedItem = new int[cols][rows];
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            rotatedItem[c][rows-1-r] = item[r][c];
        }
    }

    return rotatedItem;
}

• 시계방향으로 90도 회전된 배열의 폭과 너비 값은 서로 뒤바뀌게 된다.
• 2차원 배열을 90도 회전할 경우 좌표의 변경이 일어난다 (참고)
  • col = before_row
  • row = before_width -1 - before_row

 

전체 코드

int[][] directions = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int solution(int[][] game_board, int[][] table) {
    int answer = 0;
    List<int[][]> blanks = seek(game_board, 0);
    List<int[][]> puzzles = seek(table, 1);

    for (int[][] blank : blanks) {
        int idx = -1;
        for (int i = 0; i < puzzles.size(); i++) {
            int sum = match(blank, puzzles.get(i));
            if (sum > 0) {
                idx = i;
                answer += sum;
                break;
            }
        }

        if (idx != -1) puzzles.remove(idx);
    }

    return answer;
}

• 출처의 파이썬 코드를 자바로 변환하여 짰습니다.

 

 

 

블로그 참고

• youngyin - 프로그래머스_퍼즐 조각 채우기
• albaneo0724 - [Algorithm]2차원 행렬 회전