[프로그래머스/Java] 퍼즐 조각 채우기(BFS/DFS) 풀이

프로그래머스 알고리즘 고득점 kit의 BFS/DFS 파트의 문제인 '퍼즐 조각 채우기'를 자바로 풀어보았다.

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

프로그래머스

 

 

 접근 자체가 어렵다기보다는 그냥 조건이 아주 많고, 코드가 매우 복잡해서 하면서도 이게 맞나 하는 의구심이 계속 드는 문제이다. 사실 DFS로 접근해야 한다는 것만 알고 있으면 퍼즐을 어떻게 파악해야 할지는 어렵지 않은데, 이걸 어떻게 저장하고 비교하는지 방법을 정하는 게 어려웠다. 방법을 정해도 너무 복잡해서 뭔가 더 좋은 게 있을 것 같은 느낌이 계속 들었다. 

 

 코드가 너무 길어서 하나하나 설명하는 데는 무리가 있어 간단한 접근 방법만 언급하려 한다. (세부적인 설명은 주석으로 달아두었다.) 아래는 문제 조건에 따른 접근법이다.

 

1. 퍼즐 형태를 어떻게 파악하는가

•  dfs로 퍼즐 내부의 모든 칸을 순회하며, 시작 위치를 기준으로 한 상대위치와 퍼즐이 차지하는 칸 수를 저장한다. 
• 별도의 Puzzle class를 생성하여 정보를 저장한다.
• equals method를 override하여 퍼즐 공간이 정확히 일치하는지 비교한다. 

2. puzzle이 회전 가능하다

• table을 직접 90도씩 돌려서 그 상태에서의 일치 여부를 파악한다.
• 90도씩 돌리기 전, 이미 사용된 퍼즐은 table에서 삭제한다.
• 확인하고 90도 돌리는 작업을 4번 반복하면 모든 회전된 형태의 퍼즐을 확인할 수 있다.

3. 채워진 칸 수, 즉 답을 어떻게 구하는가

• 퍼즐을 채울 때마다, 미리 puzzle class를 통해 저장해 둔 퍼즐의 size를 answer에 더해준다.

 

 아래는 전체 코드이다. 

import java.util.*;

class Puzzle {
    int size; //puzzle이 차지하는 칸 수
    List<List<Integer>> shape; //시작점 기준 puzzle을 구성하는 상대 좌표
    
    // 새로운 퍼즐조각 생성
    Puzzle(int x, int y, int[][] table, int none) {
        shape = new ArrayList<>();
        make_puzzle(shape, x, y, table, x, y, none);
        this.size = shape.size();
        
        // shape 내 좌표들을 정렬하여 추후 비교를 편리하게 한다
        Collections.sort(shape, (a, b) -> {
            if (a.get(0) == b.get(0)) {
                return b.get(1) - a.get(1);
            } return b.get(0) - a.get(0);
        });
    }
    
    // puzzle construct 위한 helper function (dfs로 puzzle 순회)
    private void make_puzzle(List<List<Integer>> shape, int x, int y, 
                             int[][] table, int X, int Y, int none) {
        if (x < 0 || x >= table.length || y < 0 || y >= table.length) return;
        if (table[x][y] == none) return;
        
        shape.add(Arrays.asList(x-X, y-Y));
        table[x][y] = none;
        int[][] move = {{0, 1}, {1, 0}, {-1, 0}, {0 , -1}};
        for (int[] m : move) {
            make_puzzle(shape, x+m[0], y+m[1], table, X, Y, none);
        }
    }
    
    // 같은 모양의 퍼즐인지 비교
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Puzzle)) return false;
        Puzzle puzzle = (Puzzle) obj;
        return (this.size == puzzle.size) 
            && (Objects.equals(this.shape, puzzle.shape));
    }
    
    //size와 shape 같으면 같은 hash값 생성
    @Override
    public int hashCode() {
        return Objects.hash(size, shape);
    }
}

class Solution {
   // 2차원 배열 복사 (table 복사할 때 사용)
    public void copy_2d(int[][] original, int[][] copy) {
        int len = original.length;
        for (int x = 0; x < len; x++) {
            for (int y = 0; y < len; y++) {
                copy[x][y] = original[x][y];
            }
        }
    }
    
    //game board로 space 조각 list 생성
    public List<Puzzle> make_space_list(int[][] game_board) {
        List<Puzzle> list = new ArrayList<>();
        
        int len = game_board.length;        
        for (int x = 0; x < len; x++) {
            for (int y = 0; y < len; y++) {
                if (game_board[x][y] == 0) {
                    list.add(new Puzzle(x, y, game_board, 1));
                }
            }
        }
        return list;
    }

    
    public int solution(int[][] game_board, int[][] table) {
        int answer = 0;
        
        int len = table.length;
        List<Puzzle> space = make_space_list(game_board);
        
        // puzzle 만드는 재귀에서 table 값이 변경되기 때문에 원본이 아닌 copy를 넣어야 함
        int[][] table_copy = new int[len][len];
        copy_2d(table, table_copy);
        
        for (int i = 0; i < 4; i++) { 
            // 일치하는 퍼즐 조각 찾기
            for (int x = 0; x < len; x++) {
                for (int y = 0; y < len; y++) {
                    if (table_copy[x][y] == 1) {
                        Puzzle p = new Puzzle(x, y, table_copy, 0);
                        if (space.contains(p)) {
                            space.remove(p);
                            answer += p.size; //지워진 칸 세기
                            new Puzzle(x, y, table, 0); //remove p
                        }
                    }
                }
            }
            if (space.isEmpty()) return answer;
            
            // table 90도 회전
            for (int x = 0; x < len; x++) {
                for (int y = 0; y < len; y++) {
                    table_copy[x][y] = table[len-y-1][x];
                }
            }
            copy_2d(table_copy, table);
        }
        return answer;
    }
}