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

문제

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

설명

주의할 점

1. 블록이나 빈 공간의 좌표를 오름차순 정렬해야 한다.
   -> 만약 정렬되지 않으면 좌표가 뒤죽박죽 섞여서 빈 공간과 블록의 좌표를 제대로 비교할 수 없기 때문에 오름차순 정렬을 하고 나서 비교를 해야 한다. (블록을 회전시키고 난 뒤에도 오름차순 정렬을 해줘야 한다.)
2. 블록이나 빈 공간의 기준점을 (0, 0)으로 해야 한다.
   -> 블록이 게임 보드의 특정 공간에만 들어가는 것이 아니라 빈 공간을 발견하면 먼저 블록과 개수가 같은지 확인하고 회전도 시켜보기 때문에 (0, 0)을 기준으로 블록, 빈 공간의 좌표를 바꾸어야 한다. (블록을 회전시키고 난 후에도 (0, 0)을 기준으로 좌표를 변경해야 한다.)
   -> 나는 게임 보드의 빈 공간과 테이블의 블록을 찾아낼 때부터 먼저 시작점을 (0, 0)으로 해서 리스트에 넣은 다음에 나머지 좌표들은 (다음 좌표 - 현재 좌표 -> (nx - x, ny - y))를 해서 리스트에 넣어줬다.

소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

class Point implements Comparable<Point> {
    int x;
    int y;
	
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // 오름차순 정렬
    @Override
    public int compareTo(Point o) {
        if (this.x == o.x) {
            return this.y - o.y;
        }
		
        return this.x - o.x;
    }
}

public class Week03 {

    static int[] dx = {-1, 0 , 1, 0}; // 상하
    static int[] dy = {0, -1, 0, 1}; // 좌우
 	
    static int boardSize;
    static ArrayList<ArrayList<Point>> empty = new ArrayList<>(); // 게임 보드의 빈 공간 저장
    static ArrayList<ArrayList<Point>> block = new ArrayList<>(); // 테이블의 블록 저장
    static boolean[][] visited;
	
    public static void main(String[] args) {
        int[][] g1 = {{1, 1, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 0}, {0, 1, 1, 0, 0, 1}, 
				{1, 1, 0, 1, 1, 1}, {1, 0, 0, 0, 1, 0}, {0, 1, 1, 1, 0, 0}};
        int[][] t1 = {{1, 0, 0, 1, 1, 0}, {1, 0, 1, 0, 1, 0}, {0, 1, 1, 0, 1, 1}, 
				{0, 0, 1, 0, 0, 0}, {1, 1, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 0}};
		
        System.out.println(solution(g1, t1));
    }

    public static int solution(int[][] game_board, int[][] table) {
        boardSize = game_board.length;
		
        visited = new boolean[boardSize][boardSize];
		
        // 게임 보드의 빈 공간 체크
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j <boardSize; j++) {
                if (game_board[i][j] == 0 && !visited[i][j]) {
                    empty.add(check(game_board, i, j, 0));
                }
            }
        }
		
        for (int i = 0; i < boardSize; i++) {
            Arrays.fill(visited[i], false);	
        }
		
        // 테이블의 블록 체크
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                if (table[i][j] == 1 && !visited[i][j]) 
                    block.add(check(table, i, j, 1));
                }
            }
        }
		
        boolean[] visitedBoard = new boolean[empty.size()];
        int answer = 0;
	
        // 게임 보드의 빈 공간과 테이블의 블록만큼 반복하면서 빈 공간에 블록을 채움
        for (int i = 0; i < block.size(); i++) {
            ArrayList<Point> blockCheck = block.get(i);
			
            for (int j = 0; j < empty.size(); j++) {
                ArrayList<Point> emptyCheck = empty.get(j);
				
                // 빈 공간과 블록의 개수가 같고 방문한 적이 없는 곳일 경우
                if (emptyCheck.size() == blockCheck.size() && !visitedBoard[j]) {
                    // 빈 공간에 블록이 들어가는지 확인
                    if (isRotate(emptyCheck, blockCheck)) {
                        // 빈 공간에 블록이 들어간다면 answer에 블록 개수를 더함
                        answer += blockCheck.size();
                        visitedBoard[j] = true;
                        break;
                    }
                }
            }
        }
		
        return answer;
    }
	
    // 게임 보드의 빈 공간과 테이블의 블록을 찾아내는 메소드
    // 탐색할 배열, 탐색할 인덱스, 게임보드와 테이블 구분하는 변수
    public static ArrayList<Point> check(int[][] board, int x, int y, int type) {
        Queue<Point> q = new LinkedList<>();
        ArrayList<Point> result = new ArrayList<>();
		
        q.add(new Point(x, y));
        visited[x][y] = true;
		
        // 빈 공간이나 블록의 첫 번째 좌표를 (0, 0)으로 함
        result.add(new Point(0, 0));
		
        while (!q.isEmpty()) {
            Point cur = q.poll();
			
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
				
                if (nx >= 0 && nx < boardSize && ny >= 0 && ny < boardSize) {
                    if (!visited[nx][ny] && board[nx][ny] == type) {
                        q.add(new Point(nx, ny));
                        visited[nx][ny] = true;
						
                        // 기준이 (0, 0)이기 때문에 (nx - x, ny - y)를 리스트에 넣음
                        result.add(new Point(nx - x, ny - y));
                    }
                }
				
            }
        }
		
        Collections.sort(result);
		
        return result;
    }
	
    // 블록을 회전시키면서 게임 보드에 들어가는지 확인하는 메소드
    public static boolean isRotate(ArrayList<Point> empty, ArrayList<Point> block) {
        // 90도씩 회전 시키기
        for (int i = 0; i < 4; i++) {
            int zeroX = block.get(0).x;
            int zeroY = block.get(0).y;
			
            // 회전시키면서 좌표가 달라지기 때문에 다시 (0, 0)을 기준으로 블록 좌표를 변경
            for (int j = 0; j < block.size(); j++) {
                block.get(j).x -= zeroX;
                block.get(j).y -= zeroY;
            }
			
            boolean isCollect = true;
			
            for (int j = 0; j < empty.size(); j++) {
                Point emptyPoint = empty.get(j);
                Point blockPoint = block.get(j);
				
                // 블록 좌표가 빈 공간의 좌표와 하나라도 다르면 중단
                if (emptyPoint.x != blockPoint.x || emptyPoint.y != blockPoint.y) {
                    isCollect = false;
                    break;
                }
            }
			
            if (isCollect) {
                return true;
            }
            else {
                // 90도 회전 : (x, y) -> (y, -x)
                for (int j = 0; j < block.size(); j++) {
                    int temp = block.get(j).x;
					
                    block.get(j).x = block.get(j).y;
                    block.get(j).y = -temp;
                }
				
                Collections.sort(block);
            }
			
        }
		
        return false;
    }
	
}

GITHUB

https://github.com/MinchaeKwon/Programmers/blob/master/Weekly_Challenge/src/Week03.java