[JAVA] 퍼즐 조각 채우기 - 프로그래머스[Lv.3]

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

프로그래머스

---

import java.util.*;
class Solution {
    static List<List<Pos>> blocks = new ArrayList<>();
    static List<List<Pos>> emptySpace = new ArrayList<>();
    static boolean[][][] visit;
    static boolean[] isFilled;
    static int len, max = 0, spaceSize, blockSize;
    static int[][] move = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public int solution(int[][] game_board, int[][] table) {
        len = game_board.length;
        visit = new boolean[2][len][len];
        for (int i = 0; i < len; i++) { //블록 리스트 셋업, 빈 공간 셋업
            for (int j = 0; j < len; j++) {
                if (table[i][j] == 1 && !visit[1][i][j])
                    blocks.add(fillList(i, j, 1, table));
                if (game_board[i][j] == 0 && !visit[0][i][j])
                    emptySpace.add(fillList(i, j, 0, game_board));
            }
        }
        //모든 공간에 대해 블록 일치하는지 돌려보며 체크
        spaceSize = emptySpace.size();
        blockSize = blocks.size();
        max = getMaxArea();

        return max;
    }

    private int getMaxArea() {
        int ans = 0;
        isFilled = new boolean[spaceSize];

        for (int i = 0; i < blockSize; i++) {
            List<Pos> block = blocks.get(i);
            for (int j = 0; j < spaceSize; j++) {
                List<Pos> space = emptySpace.get(j);
                if(isFilled[j] || space.size() != block.size()) continue;
                if (isFit(space, block)) {
                    isFilled[j] = true;
                    ans += space.size();
                    break;
                }
            }
        }
        return ans;
    }

    private boolean isFit(List<Pos> spaceList, List<Pos> blockList) {
        //블록 4번 회전시키며 공간에 들어가는지 체크
        for (int i = 0; i < 4; i++) {
            //블록 상대좌표화
            int standX = blockList.get(0).x;
            int standY = blockList.get(0).y;

            for (Pos p : blockList) {
                p.x -= standX;
                p.y -= standY;
            }
            
            boolean flag = true;
            for (int j = 0; j < spaceList.size(); j++) {
                Pos space = spaceList.get(j);
                Pos block = blockList.get(j);
                if (space.x != block.x || space.y != block.y){
                    flag = false;
                    break;
                }
            }
            if(flag)
                return true;
            
            else {
                //회전
                for (Pos pos : blockList) {
                    int tmp = pos.x;
                    pos.x = pos.y;
                    pos.y = -tmp;
                }
            }
            Collections.sort(blockList);
        }
        return false;
    }
    
    private List<Pos> fillList(int x, int y, int SB, int[][] table) { //블록이면 1 / 빈공간이면 0 일 경우 카운팅
        List<Pos> block = new ArrayList<>();
        Queue<Pos> queue = new LinkedList<>();
        block.add(new Pos(0, 0)); //상대좌표로 넣기 위해 첫 점을 0, 0으로 맞춤
        queue.add(new Pos(x, y));
        visit[SB][x][y] = true;
        while (!queue.isEmpty()) {
            Pos now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now.x + move[i][0];
                int ny = now.y + move[i][1];
                if (nx < 0 || ny < 0 || nx >= len || ny >= len || table[nx][ny] != SB || visit[SB][nx][ny]) continue;
                queue.add(new Pos(nx, ny));
                visit[SB][nx][ny] = true;
                block.add(new Pos(nx - x, ny - y));
            }
        }
        Collections.sort(block);
        return block;
    }

    private class Pos implements Comparable<Pos> {
        int x;
        int y;

        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pos o) {
            if (this.x > o.x) return 1;
            else if (this.x < o.x) return -1;
            else {
                if (this.y > o.y) return 1;
                else return -1;
            }
        }
    }
}

💡 BFS

풀이

블럭끼리 조합해서 채워도 되는줄 알고 머리 붙잡고 쓰러질뻔;; 문제를 제발 잘보자,.....ㅠ
➕ 객체 참조까지 2연타.. 어지럽군ㅎ

• 블럭 리스트부터 갖추고 시작해야 한다..
  • 블럭 모양의 리스트를 갖추기 위해 BFS 탐색으로 블럭 좌표 리스트 확보
  • 모양이 맞는지 확인하기 위해 절대좌표 -> 상대 좌표로 변환 해 저장 (x, y 순으로 정렬 시 제일 작은 좌표 기준)
• 회전이 가능하므로 블럭에 대해 경우를 생각해야 하므로 한 공간에 대해 모든 블록을 갖다 대보면서 체크
  
  • 빈칸에 대해 블록 2개 이상을 조합해서 채울 수 없음!!! (채우는 과정에서 필연적으로 인접한 빈칸이 생기기 때문에)
  • 공간 list 1개, 블록 list 1개씩 뽑은 뒤 - 블록 list를 회전시켜가며 공간 set과 일치하는지 검사
    
    • 원래는 Set으로 하고 싶었는데 그럼 empty는 TreeSet으로 해줘야 하고... 복잡해져서 그냥 List로 함 
    • 공간 list와 블록 list가 같은지 확인
      • 같다면 해당 공간은 채웠으므로 중복 방지하기 위해 isFilled 배열 체크 해줌
      • 정답
    • 칸이 일치하지 않는 경우 : pass 
  • 한 번 회전(90도)할 때 좌표 변화 : (x, y) -> (y, -x)
  • 그러나... 왜인지 첫번째 테스트 케이스 답으로 계속 7이 나온다... 분명히 로직에 있어 틀린 부분은 없었는데!...

❗❗❗ 몇 시간을 잡아먹은 문제의 원흉 : 빈칸에 블록이 일치하는지 검사하는 과정에서 블록의 좌표들을 상대좌표화 하는 코드

//오류 코드
Pos stand = blockList.get(0);
for (Pos p : blockList) {
    p.x -= stand.x;
    p.y -= stand.y;
}

//통과 코드
int standX = blockList.get(0).x;
int standY = blockList.get(0).y;
for (Pos p : blockList) {
    p.x -= standX;
    p.y -= standY;
}​
- 그렇다,  stand객체에는 리스트 첫번째 요소의 주소가 저장되므로 두번째 Pos 부터는 stand.x, stand.y 값이 둘 다 0이 된다.
➡️ 오류 코드는 객체의 주소를 공유해 수정하고, 통과 코드는 객체의 값을 복사해 독립적으로 수정하므로 차이가 발생한 것!!

✅ 객체를 저장할 때는 객체의 참조가 저장된다 ==  완전히 독립되는 것이 아닌 공유되며 반영됨 (≒ 얕은 복사)
       반대로 int형 변수에 저장하는 경우, 객체의 값 자체가 복사돼 저장되는 것이므로 독립적으로 수정 가능

• 아래 코드처럼 수정해주니 통과했다.. ㅋㅋ .. 기본적인 걸 헷갈려서 시간을 날린게 속이 쓰리다.