[프로그래머스/Java] 84021 퍼즐 조각 채우기

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/84021

프로그래머스

 

🔍  해결 과정

문제의 조건에 맞춰서 단순 구현의 방법으로 문제를 해결할 수 있었지만 구현을 위한 과정을 세우는 데 있어서 어느 정도 시간이 걸렸던 문제였습니다. 이 문제의 해결을 위한 과정의 큰 틀은 다음과 같습니다.

1️⃣ 문제의 game_board에서 빈 공간들의 집합을 이중 연결 리스트 spaces에 저장한다. (정규화 작업을 진행한 좌표를 모아둠)
2️⃣ table에서 퍼즐들의 좌표 집합 모음을 이중 연결 리스트 puzzles에 저장한다. (정규화 작업을 진행한 좌표를 모아둠)
3️⃣ spaces와 puzzles에서 모아둔 좌표들을 바탕으로 퍼즐을 반시계 방향으로 90도 회전하며 자리가 서로 일치한지 확인한다.

 

자세한 설명은 코드에 있는 주석을 첨부하였습니다.

---

✏️ 코드

import java.util.*;

class Solution {
    
    // 방향을 위한 배열
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};
    
    public int solution(int[][] game_board, int[][] table) {
        // game_board의 빈공간을 추출하기 
        // 빈 공간도 집합으로 처리해야하므로 이중 연결 리스트를 활용하여 좌표들을 집합 형태로 저장한다.
        List<List<int[]>> spaces = getTargets(game_board, 0);
        
        // table에서의 퍼즐 조각 -> 빈 공간과 마찬가지로 이중 연결 리스트를 통해서 저장한다.
        List<List<int[]>> puzzles = getTargets(table, 1);
        
        // game_board과 table의 퍼즐 조각을 서로 비교하기
        int n = puzzles.size();
        // 퍼즐 조각이 사용됐는지 확인하기 위한 용도
        boolean[] used = new boolean[n];
        int answer = 0; // 퍼즐 조각 채운 좌표들의 개수
        
        // 퍼즐 조각과 빈 공간을 서로 비교하며 답을 추출한다.
        for (List<int[]> space : spaces) {
            boolean flag = false;
            
            for (int i = 0; i < n; ++i) {
                
                if (used[i]) {
                    continue;
                }
                
                List<int[]> puzzle = puzzles.get(i);
                
                for (int rot = 0; rot < 4; ++rot) {
                    if (match(space, puzzle)) {
                        used[i] = true;
                        flag = true;
                        answer += puzzle.size();
                        break;
                    }
                    
                    rotate(puzzle);
                }
                
                if (flag) {
                    break;
                }
            }
        }
        
        return answer;
    }
    
    // 반시계 방향으로 90도 회전하기
    private void rotate(List<int[]> puzzle) {
        // 정규화를 위한 변수
        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
        
        for (int[] p : puzzle) {
            int temp = p[0];
            p[0] = p[1];
            p[1] = -temp;
            
            minX = Math.min(minX, p[0]);
            minY = Math.min(minY, p[1]);
        }
        
        // 정규화 진행
        for (int[] p : puzzle) {
            p[0] -= minX;
            p[1] -= minY;
        }
        
        // 좌표들을 오름차순으로 정렬하기
        puzzle.sort(Comparator.comparingInt((int[] a) -> a[0])
                    .thenComparing((int[] a, int[] b) -> Integer.compare(a[1], b[1])));
    }
    
    // 좌표가 전부 일치한지 확인하기
    private boolean match(List<int[]> space, List<int[]> puzzle) {
        if (space.size() != puzzle.size()) {
            return false;
        }
        
        int n = space.size();
        
        for (int i = 0; i < n; ++i) {
            if (space.get(i)[0] != puzzle.get(i)[0] || 
               space.get(i)[1] != puzzle.get(i)[1]) {
                return false;
            }
        }
        
        return true;
    }
    
    // 보드에서 특정 좌표들을 추출하여 이중 연결리스트로 저장하기
    private List<List<int[]>> getTargets(int[][] board, int target) {
        int len = board.length;
        boolean[][] visited = new boolean[len][len];
        List<List<int[]>> result = new ArrayList<>();
        
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                if (visited[i][j] || board[i][j] != target) {
                    continue;
                }
                
                result.add(bfs(board, len, visited, i, j, target));
            }
        }
        
        return result;
    }
    
    // bfs를 활용하여 보드에서 특정 좌표들을 리스트 형태로 담아둔다.
    private List<int[]> bfs(int[][] board, int n, boolean[][] visited, 
                            int r, int c, int target) {
        Queue<int[]> q = new ArrayDeque<>();
        List<int[]> pairs = new ArrayList<>();
        List<int[]> result = new ArrayList<>(); 
        visited[r][c] = true;
        q.offer(new int[]{r, c});
        pairs.add(new int[]{r, c});
        int minX = r, minY = c;
        
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            minX = Math.min(x, minX);
            minY = Math.min(y, minY);
            for (int dir = 0; dir < 4; ++dir) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                    continue;
                }
                
                if (visited[nx][ny] || board[nx][ny] != target) {
                    continue;
                }
                
                q.offer(new int[]{nx, ny});
                visited[nx][ny] = true;
                pairs.add(new int[]{nx, ny});
            }
        }
        
        // 정규화 작업 진행하기
        for (int[] pair : pairs) {
            result.add(new int[]{pair[0] - minX, pair[1] - minY});
        }
        
        // 정규화 작업 진행 후 정렬하기
        result.sort(Comparator.comparingInt((int[] a) -> a[0])
                    .thenComparing((int[] a, int[] b) -> Integer.compare(a[1], b[1])));
        
        return result;
    }
}