[lv.3] 퍼즐 조각

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

• 문제

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

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

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

  

• 풀이
  1) 퍼즐 조각을 bfs로 찾고, 찾은 퍼즐조각을 칸 개수와 좌표의 리스트 형태의 객체 Puzzle로 저장한다.
  2) 비어있는 곳을 bfs로 찾고, 찾은 빈 부분과 퍼즐 조각을 매칭시킨다.
  2-1) 칸 개수가 맞는지 확인한다.
  2-2) 두 좌표의 리스트를 x좌표, y좌표 순으로 정렬하고, 두 좌표의 리스트의 좌표 차이를 반영하여 비교한다.
  2-3) 맞지 않을 경우 3번 정도 90도 회전을 하여 비교하여 맞는지 확인한다. ((x, y)->(y, -x))

Collections.sort(list1, (o1, o2) -> {
	if (o1[0] != o2[0]) {
		return Integer.compare(o1[0], o2[0]);
	} else {
		return Integer.compare(o1[1], o2[1]);
	}
});

• 소감
  풀이 자체는 어렵지 않으나 구현이 진짜 존나 빡셌던 문제
  두번정도 막혔었는데 90도 회전과 ArrayList<int[]>의 정렬이다. 기억하자.
  구현까지 다 하는데 2시간 걸렸다.
  이거 네이버 코테 문제였다는데 이런 문제가 가득한 것을 2시간내로 풀고 합격하는 사람들은 대체...

• 코드

import java.util.*;

class Puzzle{
    int cnt;
    ArrayList<int[]> points = new ArrayList<>();
    public Puzzle(int cnt, ArrayList<int[]> points){
        this.cnt = cnt;
        this.points = points;
    }
    public ArrayList<int[]> rotate(){
        ArrayList<int[]> newPoints = new ArrayList<>();
        for(int[] arr : points){
            newPoints.add(new int[]{arr[1], -1*arr[0]});
        }
        return newPoints;
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append(cnt+" ");
        for(int[] p : points){
            sb.append(p[0]+"-"+p[1]+" ");
        }
        return sb.toString();
    }
}

class Empty{
    int cnt;
    ArrayList<int[]> points = new ArrayList<>();
    public Empty(int cnt, ArrayList<int[]> points){
        this.cnt = cnt;
        this.points = points;
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append(cnt+" ");
        for(int[] p : points){
            sb.append(p[0]+"-"+p[1]+" ");
        }
        return sb.toString();
    }
}

class Solution {
    static boolean[][] check;
    static ArrayList<Puzzle> pList = new ArrayList<>();
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int n;
    public int solution(int[][] game_board, int[][] table) {
        int answer = 0;
        n = table.length;
        check = new boolean[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(table[i][j]==1 && !check[i][j]) findPuzzle(i, j, table);
            }
        }
        check = new boolean[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(game_board[i][j]==0 && !check[i][j]){
                    Empty e = findEmpty(i, j, game_board);
                    for(Puzzle p : pList){
                        //System.out.print(p+"----- "+e);
                        if(canInsert(p, e)){
                            answer += p.cnt;
                            //System.out.println("......OK");
                            pList.remove(p);
                            break;
                        }
                        //System.out.println();
                    }
                }
            }
        }
        return answer;
    }
    public boolean canInsert(Puzzle p, Empty e){
        if(p.cnt != e.cnt) return false;
        if(isSame(p.cnt, p.points, e.points)) return true;
        else{
            for(int i=0; i<3; i++){
                p.points = p.rotate();
                if(isSame(p.cnt, p.points, e.points)) return true;
            }
        }
        return false;
    }
    public boolean isSame(int size, ArrayList<int[]> list1, ArrayList<int[]> list2){
        Collections.sort(list1, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return Integer.compare(o1[0], o2[0]);
            } else {
                return Integer.compare(o1[1], o2[1]);
            }
        });
        Collections.sort(list2, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return Integer.compare(o1[0], o2[0]);
            } else {
                return Integer.compare(o1[1], o2[1]);
            }
        });
        int xd = list1.get(0)[0] - list2.get(0)[0];
        int yd = list1.get(0)[1] - list2.get(0)[1];
        for(int i=1; i<size; i++){
            int[] p1 = list1.get(i);
            int[] p2 = list2.get(i);
            if((p2[0]+xd!=p1[0]) || (p2[1]+yd!=p1[1])) return false;
        }
        return true;
    }
    public void findPuzzle(int x, int y, int[][] table){
        Queue<int[]> queue = new LinkedList<>();
        ArrayList<int[]> points = new ArrayList<>();
        check[x][y] = true;
        queue.add(new int[]{x, y});
        points.add(new int[]{x, y});
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            for(int i=0; i<4; i++){
                int nx = now[0]+dx[i];
                int ny = now[1]+dy[i];
                if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
                if(check[nx][ny] || table[nx][ny]==0) continue;
                queue.add(new int[]{nx, ny});
                check[nx][ny] = true;
                points.add(new int[]{nx, ny});
            }
        }
        Puzzle p = new Puzzle(points.size(), points);
        pList.add(p);
    }
    public Empty findEmpty(int x, int y, int[][] game_board){
        Queue<int[]> queue = new LinkedList<>();
        ArrayList<int[]> points = new ArrayList<>();
        check[x][y] = true;
        queue.add(new int[]{x, y});
        points.add(new int[]{x, y});
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            for(int i=0; i<4; i++){
                int nx = now[0]+dx[i];
                int ny = now[1]+dy[i];
                if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
                if(check[nx][ny] || game_board[nx][ny]==1) continue;
                queue.add(new int[]{nx, ny});
                check[nx][ny] = true;
                points.add(new int[]{nx, ny});
            }
        }
        return new Empty(points.size(), points);
    }
}