[프로그래머스 Level.3] 퍼즐 조각 채우기 (깊이/너비 우선 탐색(DFS/BFS)) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 퍼즐 조각 채우기

 

 

 

문제 설명

 

 

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

 

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

 

다음은 퍼즐 조각을 채우는 예시입니다.

 

 

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

 

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

 

 

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

 

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

 

 

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

 

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

---

제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

 

---

 

입출력 예

game_board	table	result
[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]	[[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]	14
[[0,0,0],[1,1,0],[1,1,1]]	[[1,1,1],[1,0,0],[0,0,0]]	0

 

---

 

입출력 예 설명

 

 

입출력 예 #1

 

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

 

 

 

 

입출력 예 #2

 

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

 

 

 

 

 

 

나의 코드

import java.util.*;

// 참고:https://tmdrl5779.tistory.com/206
// https://velog.io/@minchae75/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Java-%ED%8D%BC%EC%A6%90-%EC%A1%B0%EA%B0%81-%EC%B1%84%EC%9A%B0%EA%B8%B0
class Solution {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    public int solution(int[][] game_board, int[][] table) {
        int answer = 0;
        
        boolean[][] boardVisited = new boolean[game_board.length][game_board.length];
        boolean[][] tableVisited = new boolean[table.length][table.length];
        
        ArrayList<ArrayList<int[]>> boardList = new ArrayList<>();
        ArrayList<ArrayList<int[]>> tableList = new ArrayList<>();
        
        for(int i=0; i<game_board.length; i++) {
            for(int j=0; j<game_board.length; j++) {
                if(game_board[i][j] == 0 && !boardVisited[i][j]) {
                    bfs(i, j, 0, game_board, boardVisited, boardList);
                }
                
                if(table[i][j] == 1 && !tableVisited[i][j]) {
                    bfs(i, j, 1, table, tableVisited, tableList);
                }
            }
        }
        
        boolean[] visited = new boolean[boardList.size()];
        
        for(int i=0; i<tableList.size(); i++) {
            ArrayList<int[]> tablePoints = tableList.get(i);
            
            for(int j=0; j<boardList.size(); j++) {
                ArrayList<int[]> boardPoints = boardList.get(j);
                
                if(tablePoints.size() == boardPoints.size() && !visited[j]) {
                    if(checkPuzzle(boardPoints, tablePoints)) {
                        answer += tablePoints.size();
                        visited[j] = true;
                        break;
                    }
                }
            }
        }
        
        return answer;
    }
    
    public void bfs(int x, int y, int status, int[][] matrix, boolean[][] visited, ArrayList<ArrayList<int[]>> list) {
        ArrayList<int[]> tempList = new ArrayList<>();
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x, y});
        tempList.add(new int[] {x-x, y-y});
        visited[x][y] = true;

        while(!q.isEmpty()) {
            int[] now = q.poll();
            int sx = now[0];
            int sy = now[1];
            
            for(int i=0; i<4; i++) {
                int nx = sx + dy[i];
                int ny = sy + dx[i];
                
                if(nx < 0 || ny < 0 || nx >= matrix.length || ny >= matrix.length || visited[nx][ny] || matrix[nx][ny] != status) continue;
                
                visited[nx][ny] = true;
                q.add(new int[] {nx, ny});
                tempList.add(new int[] {nx-x, ny-y});
            }
        }
        
        list.add(tempList);
    }
    
    public boolean checkPuzzle(ArrayList<int[]> boardPoints, ArrayList<int[]> tablePoints) {
        boolean correctPuzzle = true;
        
        // board 좌표 정렬
        Collections.sort(boardPoints, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]); 
        
        for(int i=0; i<4; i++) {
            correctPuzzle = true;
            
            // 퍼즐 조각 회전 했으니 다시 좌표 정렬
            Collections.sort(tablePoints, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]); 
            
            // 회전했으니 다시 좌표 (0, 0)을 기준으로 조정
            int zeroX = tablePoints.get(0)[0];
            int zeroY = tablePoints.get(0)[1];
            for(int j=0; j<tablePoints.size(); j++) {
                tablePoints.get(j)[0] -= zeroX;
                tablePoints.get(j)[1] -= zeroY;
            }
            
            for(int j=0; j<tablePoints.size(); j++) {
                int[] boardPoint = boardPoints.get(j);
                int[] tablePoint = tablePoints.get(j);
                if(boardPoint[0] != tablePoint[0] || boardPoint[1] != tablePoint[1]) {
                    correctPuzzle = false;
                    break;
                }
            }
            
            if(correctPuzzle) return true;
                
            // 좌표 90도 회전 : (x,y) = (-y,x) => 배열 90도 회전 -> [x][y] = [y][-x]
            for(int j=0; j<tablePoints.size(); j++) {
                int temp = tablePoints.get(j)[0];
                tablePoints.get(j)[0] = tablePoints.get(j)[1];
                tablePoints.get(j)[1] = -temp;
            }
        }
        
        return false;
    }
    
}

 

풀이

1. 우선 game_board에서 빈 공간을 찾을 때마다 bfs를 이용하여 해당 좌표들의 세트를 구해 담고 table의 퍼즐 조각 부분을 찾을 때마다 bfs를 이용하여 해당 좌표들의 세트를 구해 담는다.
2. 좌표들을 찾으면 해당 퍼즐이 맞는지 확인해야 하므로 (0, 0)을 기준으로 좌표들을 조정해서 담아 빈 공간과 퍼즐을 비교할 수 있도록 한다. (연결된 좌표(nx, ny) - bfs 시작 좌표(x, y)를 하면 (0, 0)을 기준으로 조정 할 수 있다.) 하나의 연결된 빈 공간 또는 하나의 퍼즐 조각을 찾아 임시 리스트에 담고 이 임시 리스트를 다시 boardList 또는 tableList에 담아가며 여러 개의 빈 공간과, 퍼즐 조갇들을 갖는 리스트를 만든다.
3. 이제 빈 공간 좌표 세트들과 퍼즐 조각 세트들을 구했으니 퍼즐 조각이 맞는 빈 공간을 찾아야 한다. 퍼즐 조각들을 순회하면서 퍼즐 조각마다 빈 공간들을 다시 순회하면서 맞는 빈 공간이 있는지 확인하도록 한다.
4. 퍼즐 조각과 빈 공간의 사이즈가 같은지와 빈 공간의 체크테이블을 먼저 확인한다. 그리고 빈 공간 좌표들과 퍼즐 조각 좌표들이 (0, 0)을 기준으로 조정되어 있지만 좌표의 순서가 다를 수 있기 때문에 빈 공간 좌표와 퍼즐 조각 좌표를 각각 오름차순 정렬하여 좌표들이 모두 같은지 확인한다. 모두 같다면 해당 퍼즐 조각과 빈 공간이 맞는 것이므로 answer에 해당 퍼즐 크기만큼을 증가시켜주고 해당 빈 공간의 체크테이블을 체크해주면 되고 아니라면 퍼즐을 시계 방향으로 90도씩 회전(좌표 90도 회전 : (x,y) = (-y,x) => 배열 90도 회전 -> [x][y] = [y][-x]) 시켜 가며 다시 확인하도록 한다. (물론 퍼즐 조각을 90도씩 회전 시킬 때마다 다시 오름차순으로 정렬한 후에 빈 공간과 비교하도록 한다)
5. 퍼즐을 모두 순회하며 퍼즐이 맞는 빈 공간이 있다면 찾아 채우며 answer에 퍼즐 조각의 크기만큼 증가시켰으므로 answer를 반환하면 된다.

 

 

 

 

참고

https://tmdrl5779.tistory.com/206

https://velog.io/@minchae75/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Java-%ED%8D%BC%EC%A6%90-%EC%A1%B0%EA%B0%81-%EC%B1%84%EC%9A%B0%EA%B8%B0