[프로그래머스 알고리즘 고득점 Kit][깊이/너비 우선 탐색(DFS/BFS)][Java] 퍼즐 조각 채우기

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

프로그래머스

 

뭔가 동작이 필요할 때마다 메서드를 분리했더니 엉망이 되어버린 코드...
문제가 생겼는데 혼자 고칠 수가 없어서 지피티의 많은 도움을 받았다...

무작정 메서드 분리하는 것이 오히려 마이너스임을 깨달았다...
나를 조금 덜 믿고 메서드 별로 테스트하자...

 

 

정답 코드

 

1. table에서 블록을 찾는다.

2. game_board에서 빈칸을 찾는다.

3. BFS로 연결된 칸들을 Shape로 묶는다.

4. Shape를 정규화해서 위치 차이를 없앤다.
 -> 정렬과 0,0 시작점 일치를 강제 해줬다. 

5. 빈칸마다 사용하지 않은 블록을 하나씩 비교한다.

6. 블록을 90도씩 회전하며 같은 모양인지 확인한다.

7. 맞는 블록을 찾으면 사용 처리하고 칸 수를 더한다.

import java.util.*;

class Solution {
    final int[] dx = {-1, 1, 0, 0};
    final int[] dy = {0, 0, -1, 1};

    class Shape {
        List<Point> points = new ArrayList<>();

        void add(Point point) {
            points.add(point);
        }

        int size() {
            return points.size();
        }

        void sort() {
            Collections.sort(points, (p1, p2) -> {
                if (p1.x == p2.x) return p1.y - p2.y;

                return p1.x - p2.x;
            });
        }

        Shape normalize() {
            Shape normalizedShape = new Shape();

            int minX = Integer.MAX_VALUE;
            int minY = Integer.MAX_VALUE;

            for (Point p : points) {
                int x = p.x;
                int y = p.y;

                minX = Math.min(x, minX);
                minY = Math.min(y, minY);
            }

            for (Point p : points) {
                normalizedShape.add(new Point(p.x - minX, p.y - minY));
            }

            normalizedShape.sort();

            return normalizedShape;
        }

        Shape rotate90() {
            Shape rotatedShape = new Shape();

            for (Point p : points) {
                rotatedShape.add(new Point(p.y, p.x * -1));
            }

            return rotatedShape;
        }

        boolean isSameShape(Shape other) {
            if (this.size() != other.size()) return false;

            for (int i = 0; i < this.size(); i++) {
                Point p1 = this.points.get(i);
                Point p2 = other.points.get(i);

                if (p1.x != p2.x || p1.y != p2.y) return false;
            }

            return true;
        }
    }

    class Point {
        int x;
        int y;

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

    public int solution(int[][] game_board, int[][] table) {
        List<Shape> blocks = new ArrayList<>();
        List<Shape> blanks = new ArrayList<>();

        saveShape(blocks, table, 1);
        saveShape(blanks, game_board, 0);

        int ans = 0;
        int blockCnt = blocks.size();
        boolean[] usedBlock = new boolean[blockCnt];

        for (Shape blank : blanks) {
            for (int i = 0; i < blockCnt; i++) {
                if (usedBlock[i]) continue;

                if (canFit(blocks.get(i), blank)) {
                    usedBlock[i] = true;

                    ans += blocks.get(i).size();
                    break;
                }
            }
        }

        return ans;
    }

    public boolean canFit(Shape block, Shape blank) {
        Shape rotatedBlock = block;

        for (int i = 0; i < 4; i++) {
            if (rotatedBlock.isSameShape(blank)) return true;

            rotatedBlock = rotatedBlock.rotate90().normalize();
        }

        return false;
    }

    public void saveShape(List<Shape> shapes, int[][] map, int target) {
        int xLen = map.length;
        int yLen = map[0].length;
        boolean[][] visited = new boolean[xLen][yLen];

        for (int x = 0; x < xLen; x++) {
            for (int y = 0; y < yLen; y++) {
                if (visited[x][y] || map[x][y] != target) continue;

                Shape shape = findShapeByBFS(x, y, map, visited, target);
                shapes.add(shape.normalize());
            }
        }
    }

    public Shape findShapeByBFS(int x, int y, int[][] map, boolean[][] visited, int target) {
        Shape shape = new Shape();

        Point start = new Point(x, y);
        shape.add(start);

        Queue<Point> q = new ArrayDeque<>();
        q.add(start);
        visited[x][y] = true;

        while (!q.isEmpty()) {
            Point curr = q.poll();
            int cx = curr.x;
            int cy = curr.y;

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx < 0 || nx >= map.length || ny < 0 || ny >= map[0].length || visited[nx][ny]) continue;

                if (map[nx][ny] != target) continue;

                shape.add(new Point(nx, ny));
                visited[nx][ny] = true;
                q.add(new Point(nx, ny));
            }
        }

        return shape;
    }
}

요즘 쉬운 문제들만 풀었더니... 
조금만 복잡해져도 숨을 헐떡인다...
다시 문제만 봐도 현기증 나는 애들로 골라 풀어야겠다...