nonneng.ee
Daeun-rithm
nonneng.ee
전체 방문자
오늘
어제
  • 분류 전체보기 (51)
    • Back-end (17)
      • Server (3)
      • Database (3)
      • Spring (9)
      • Node.js (1)
    • Book (1)
      • 이펙티브 자바 (0)
      • 대규모 시스템 설계 (1)
    • Algorithm (1)
      • Greedy, Implementation (6)
      • Dynamic Programming (5)
      • Data Structure (3)
      • Sorting (2)
      • Concept (1)
    • TIL (11)
    • Software (3)
      • Design Pattern (3)
    • Computer Science (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 에러
  • 백준
  • 아이템 23
  • Restful API
  • MySQL
  • 아이템9
  • 이펙티브 자바
  • APM
  • 구현
  • 컴파일설치
  • jwt
  • 아이템 25
  • 파이썬
  • 아이템8
  • Postman
  • 우분투
  • DP
  • 구동원리
  • Spring
  • 브루트포스
  • 자바
  • 서버
  • JPA
  • node js
  • 아이템6
  • API
  • Java
  • 가상머신
  • 수동설치
  • 소스설치

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
nonneng.ee

Daeun-rithm

어떻게 알고리즘 문제 하나에 코드가 151줄?
Algorithm

어떻게 알고리즘 문제 하나에 코드가 151줄?

2025. 1. 9. 14:17

 

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

프로그래머스 Lv3. 퍼즐 조각 채우기

작년에 풀다말았던 문제를 다시 풀어보았다.

왜 풀다 말았는지 알 것 같다.

요약하자면 table에 놓인 조각들을 game_board에 딱 맞게 최대한 많이 테트리스하면 되는 문제이다.

하지만 테트리스는 조각을 돌려가며 끼울 수 있다는 점~

 

어떻게 풀지?

불규칙한 조각들을 하나씩 돌리는 것 보단 고정된 game_board를 돌리는게 나아보인다.

퍼즐조각을 끼웠을 때, 인접한 칸이 비어있으면 안되므로 특정 조각이 들어갈 수 있는 칸은 정해져있다.

따라서 들어가기만 한다면, 최대 개수를 고려할 필요가 없다. 들어가기만 하면 ok!

 

따라서

  1. table에 놓인 퍼즐조각들을 bfs로 구분하여 저장한다.
    • 조각들을 (0,0)기준으로 정규화하여 표현해둔다.
  2. game_board를 90도씩 돌려가며 bfs를 통해 빈공간을 찾는다.
    • 빈공간 역시 (0,0) 기준으로 정규화하여 표현해둔다.
  3. 빈공간에 정규화된 퍼즐조각이 들어맞는지 확인한다.

 

직접 작성해보자.

  1. table에 놓인 퍼즐조각들을 bfs로 구분하여 저장한다 → 평범한 bfs 코드를 작성하면 된다.
private void bfs(int[][] board, int x, int y, int target, int mark, List<List<List<Integer>>> blocks) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        board[x][y] = mark;
        
        List<List<Integer>> block = new ArrayList<>();
        block.add(new ArrayList<>());
        block.add(new ArrayList<>());
        block.get(0).add(x);
        block.get(1).add(y);
        
        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int cX = current[0];
            int cY = current[1];
            
            for(int i = 0; i < 4; i++) {
                int nX = cX + dx[i];
                int nY = cY + dy[i];
                
                if(nX < 0 || nY < 0 || nX >= size || nY >= size) continue;
                
                if(board[nX][nY] == target) {
                    board[nX][nY] = mark;
                    queue.add(new int[]{nX, nY});
                    block.get(0).add(nX);
                    block.get(1).add(nY);
                }
            }
        }
        blocks.add(normalize(block));
    }

조각들이 완성되면, normalize() 함수를 통해 정규화된 형태로 리스트에 추가한다.

private List<List<Integer>> normalize(List<List<Integer>> block) {
        List<List<Integer>> normalized = new ArrayList<>();
        normalized.add(new ArrayList<>());
        normalized.add(new ArrayList<>());
        
        // 최소 x, y 찾기
        int minX = Collections.min(block.get(0));
        int minY = Collections.min(block.get(1));
        
        // 모든 좌표를 (0,0) 기준으로 이동
        for(int i = 0; i < block.get(0).size(); i++) {
            normalized.get(0).add(block.get(0).get(i) - minX);
            normalized.get(1).add(block.get(1).get(i) - minY);
        }
        
        return normalized;
    }

 

 

2. game_board의 빈공간을 찾는다

→ 퍼즐조각을 찾을 때와 동일하게 bfs를 돌려준다. 하지만 빈공간을 찾는거니까 mark 매개변수로 0과 1을 구분해준다.

 

3. 빈공간에 정규화된 퍼즐조각이 들어맞는지 확인한다.

public boolean isMatch(List<List<Integer>> board, List<List<Integer>> table) {
        if(board.get(0).size() != table.get(0).size()) return false;
        
        for(int r = 0; r < 4; r++) {
            List<List<Integer>> rotated = rotate(table, r);
            rotated = normalize(rotated);
            
            // 좌표 정렬
            List<String> boardPoints = new ArrayList<>();
            List<String> tablePoints = new ArrayList<>();
            
            for(int i = 0; i < board.get(0).size(); i++) {
                boardPoints.add(board.get(0).get(i) + "," + board.get(1).get(i));
                tablePoints.add(rotated.get(0).get(i) + "," + rotated.get(1).get(i));
            }
            
            Collections.sort(boardPoints);
            Collections.sort(tablePoints);
            
            if(boardPoints.equals(tablePoints)) return true;
        }
        
        return false;
    }
  • 블록의 크기 검사
  • board를 90도씩 회전하면서 비교하기
    • 회전된 블록을 다시 (0,0) 기준으로 정규화하고
    • 좌표들을 정렬한 다음 일치하는지 비교하면
    • 정렬된 좌표 리스트가 완전히 일치하면 들어맞는다고 판단한다.

 

최종 코드

import java.util.*;

class Solution {
    int size = 0;
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    List<List<List<Integer>>> tableBlocks;
    List<List<List<Integer>>> boardBlocks;
    boolean[] used;
    
    public int solution(int[][] game_board, int[][] table) {
        size = game_board.length;
        tableBlocks = new ArrayList<>();
        boardBlocks = new ArrayList<>();
        int answer = 0;
        
        // 게임 보드의 빈 공간 찾기
        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                if(game_board[i][j] == 0) {
                    bfs(game_board, i, j, 0, 1, boardBlocks);
                }
            }
        }
        
        // 테이블의 블록 찾기
        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                if(table[i][j] == 1) {
                    bfs(table, i, j, 1, 0, tableBlocks);
                }
            }
        }
        
        used = new boolean[tableBlocks.size()];
        
        // 각 보드의 빈 공간에 대해 맞는 블록 찾기
        for(List<List<Integer>> boardBlock : boardBlocks) {
            for(int i = 0; i < tableBlocks.size(); i++) {
                if(used[i]) continue;
                
                List<List<Integer>> tableBlock = tableBlocks.get(i);
                if(isMatch(boardBlock, tableBlock)) {
                    used[i] = true;
                    answer += boardBlock.get(0).size();
                    break;
                }
            }
        }
        
        return answer;
    }
    
    private List<List<Integer>> normalize(List<List<Integer>> block) {
        List<List<Integer>> normalized = new ArrayList<>();
        normalized.add(new ArrayList<>());
        normalized.add(new ArrayList<>());
        
        // 최소 x, y 찾기
        int minX = Collections.min(block.get(0));
        int minY = Collections.min(block.get(1));
        
        // 모든 좌표를 (0,0) 기준으로 이동
        for(int i = 0; i < block.get(0).size(); i++) {
            normalized.get(0).add(block.get(0).get(i) - minX);
            normalized.get(1).add(block.get(1).get(i) - minY);
        }
        
        return normalized;
    }
    
    private void bfs(int[][] board, int x, int y, int target, int mark, List<List<List<Integer>>> blocks) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        board[x][y] = mark;
        
        List<List<Integer>> block = new ArrayList<>();
        block.add(new ArrayList<>());
        block.add(new ArrayList<>());
        block.get(0).add(x);
        block.get(1).add(y);
        
        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int cX = current[0];
            int cY = current[1];
            
            for(int i = 0; i < 4; i++) {
                int nX = cX + dx[i];
                int nY = cY + dy[i];
                
                if(nX < 0 || nY < 0 || nX >= size || nY >= size) continue;
                
                if(board[nX][nY] == target) {
                    board[nX][nY] = mark;
                    queue.add(new int[]{nX, nY});
                    block.get(0).add(nX);
                    block.get(1).add(nY);
                }
            }
        }
        blocks.add(normalize(block));
    }
    
    public boolean isMatch(List<List<Integer>> board, List<List<Integer>> table) {
        if(board.get(0).size() != table.get(0).size()) return false;
        
        for(int r = 0; r < 4; r++) {
            List<List<Integer>> rotated = rotate(table, r);
            rotated = normalize(rotated);
            
            // 좌표 정렬
            List<String> boardPoints = new ArrayList<>();
            List<String> tablePoints = new ArrayList<>();
            
            for(int i = 0; i < board.get(0).size(); i++) {
                boardPoints.add(board.get(0).get(i) + "," + board.get(1).get(i));
                tablePoints.add(rotated.get(0).get(i) + "," + rotated.get(1).get(i));
            }
            
            Collections.sort(boardPoints);
            Collections.sort(tablePoints);
            
            if(boardPoints.equals(tablePoints)) return true;
        }
        
        return false;
    }
    
    public List<List<Integer>> rotate(List<List<Integer>> block, int rotateCount) {
        List<List<Integer>> rotated = new ArrayList<>();
        rotated.add(new ArrayList<>());
        rotated.add(new ArrayList<>());
        
        for(int i = 0; i < block.get(0).size(); i++) {
            int x = block.get(0).get(i);
            int y = block.get(1).get(i);
            
            for(int r = 0; r < rotateCount; r++) {
                int temp = x;
                x = y;
                y = -temp;
            }
            
            rotated.get(0).add(x);
            rotated.get(1).add(y);
        }
        
        return rotated;
    }
}

 

하나씩 뜯어보면 어려운건 없지만 풀다보면 화나서 끈기가 필요한 문제

    nonneng.ee
    nonneng.ee

    티스토리툴바