[99클럽 코테 스터디 3일차 TIL] BFS

📖 오늘의 학습 키워드
BFS

오늘의 회고

문제

[퍼즐 조각 채우기]
https://school.programmers.co.kr/learn/courses/30/lessons/84021

나의 해결

import java.util.*;
class Solution {
    public List<List<int[]>> gameBoard;
    public List<List<int[]>> Table;
    public boolean[][] visited;
    public boolean[] visitedPuzzle;
    public int len, answer;
    public int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int solution(int[][] game_board, int[][] table) {
        answer = 0;
        len = game_board.length;
        gameBoard = new ArrayList<>();
        Table = new ArrayList<>();
        visited = new boolean[len][len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if(!visited[i][j] && table[i][j] == 1){
                    bfs(i, j, 1, table);
                }
            }   
        }
        visited = new boolean[len][len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if(!visited[i][j] && game_board[i][j] == 0){
                    bfs(i, j, 0, game_board);
                }
            }   
        }
        visitedPuzzle = new boolean[Table.size()];
        for(int i = 0; i < gameBoard.size(); i++) {
            checkPuzzle(i);
        }
        return answer;
    }
    public void bfs(int i, int j, int target, int[][] board) {
        Queue<int[]> q = new LinkedList<>();
        List<int[]> temp = new ArrayList<>();
        visited[i][j] = true;
        q.offer(new int[]{i, j});
        temp.add(new int[] {0, 0});
        while(!q.isEmpty()){
            int[] now = q.poll();
            for(int[] d : directions){
                int y = now[0] + d[0];
                int x = now[1] + d[1];
                if(x >= 0 && x < len && y >= 0 && y < len && board[y][x] == target && !visited[y][x]) {
                    q.offer(new int[]{y, x});
                    temp.add(new int[]{y-i, x-j});
                    visited[y][x] = true;
                }
            }
        }
        if(target == 0) {
            gameBoard.add(temp);
        }
        else {
            Table.add(temp);
        }
    }
    public void checkPuzzle(int idx) {
        List<int[]> board = gameBoard.get(idx);
        for(int i = 0; i < Table.size(); i++) {
            List<int[]> table = Table.get(i);
            if(!visitedPuzzle[i] && table.size() == board.size()) {
                if(isFit(board, table)){
                    answer += table.size();
                    visitedPuzzle[i] = true;
                    break;
                }
            } 
        }
    }
    public boolean isFit(List<int[]> board, List<int[]> table){
        board.sort((a, b) -> {
            if(a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        for(int i = 0; i < 4; i++) {
            table.sort((a, b) -> {
                if(a[0] == b[0]) {
                    return a[1] - b[1];
                }
                return a[0] - b[0];
            });
            int startY = table.get(0)[0];
            int startX = table.get(0)[1];
            for(int j = 0; j < table.size(); j++) {
                table.get(j)[0] -= startY;
                table.get(j)[1] -= startX;
            }
            boolean fit = true;
            for(int j = 0; j < table.size(); j++) {
                int[] currTable = table.get(j);
                int[] currBoard = board.get(j);
                if(currTable[0] != currBoard[0] || currTable[1] != currBoard[1]) {
                    fit = false;
                    break;
                }
            }
            if(!fit){
                for(int j = 0; j < table.size(); j++) {
                    int temp = table.get(j)[0] * -1;
                    table.get(j)[0] = table.get(j)[1];
                    table.get(j)[1] = temp;
                }
            }
            else {
                return true;
            }
        }
        return false;
    }
}

1. BFS를 사용해서 게임보드에서의 빈 칸에 대한 정보와 테이블 위의 퍼즐 조각에 대한 정보(개수와 크기)를 저장한다.
   • BFS를 이용해 각 빈칸과 퍼즐 조각를 구성하는 좌표값을 저장한다. BFS의 시작 격자의 좌표를 (0, 0)으로 간주하고 나머지 격자의 상대 좌표를 구해 저장한다.
2. 게임보드 위 빈칸들 하나씩 각각의 퍼즐 조각과 대조하며 조각이 빈칸에 맞는지 확인하다.
   • 중복 확인을 막기 위해 테이블 위 퍼즐 조각에 대한 방문 배열을 만든다.
   • 빈칸을 구성하는 격자의 개수와 퍼즐 조각의 격자의 개수가 다르다면 굳이 비교하지 않다.
   • 90, 180, 270도 회전하면서 해당 퍼즐이 빈칸에 맞는지 확인한다.
     90도 시계방향 회전 : (y, x) -> (x, -y)

새로 학습한 내용

필요한 알고리즘을 떠올리는 데는 어렵지 않았으나 필요한 함수들을 구현하는 데 많은 시간이 필요했다. 코드를 작성하기 전에 필요한 함수와 변수들을 잘 정리해야겠다는 생각이 들었다. 그리고 좌표 회전 방법이 바로 떠오르지 않아 생각보다 여기서 시간을 많이 지체했다. 앞으로 이를 잘 기억해 두어야겠다.