프로그래머스: 퍼즐 조각 맞추기⭐⭐⭐
카테고리: Programmers
태그: Algorithm, Blog, C++, Programmers
난이도 ⭐⭐⭐
유형 : DFS/BFS(탐색), 구현
🧐 문제
문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
- 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
- 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 3 ≤
game_board의 행 길이 ≤ 50 game_board의 각 열 길이 =game_board의 행 길이- 즉, 게임 보드는 정사각 격자 모양입니다.
game_board의 모든 원소는 0 또는 1입니다.- 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
- 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
table의 행 길이 =game_board의 행 길이table의 각 열 길이 =table의 행 길이- 즉, 테이블은
game_board와 같은 크기의 정사각 격자 모양입니다. table의 모든 원소는 0 또는 1입니다.- 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
- 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
- 즉, 테이블은
game_board에는 반드시 하나 이상의 빈칸이 있습니다.table에는 반드시 하나 이상의 블록이 놓여 있습니다.
입출력 예
| game_board | table | result |
|---|---|---|
| [[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]] | [[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]] | 14 |
| [[0,0,0],[1,1,0],[1,1,1]] | [[1,1,1],[1,0,0],[0,0,0]] | 0 |
입출력 예 설명
접기/펼치기
**입출력 예 #1**
입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.
블록의 회전은 가능하지만, 뒤집을 수는 없습니다.
🔍 풀이
이번 문제는 알고리즘이랄건 없고, 구현에 매우 치중된 문제입니다.
보드와 테이블을 DFS/BFS를 통해 돌며, 사진과 같이 조각을 분리하여 배열에 저장해둡니다.
이때 조각의 칸 수 또한 저장해두도록 합니다.
그리고 이중포문을 돌며 game_board에서 조각 하나, table에서 조각 하나를 꺼냅니다.
table에서 꺼낸 조각을 90도씩 돌려가며, game_board에서 꺼낸 조각과 비교합니다.
같다면 총 조각 칸 수를 추가하고, table에서 꺼낸 조각 하나는 방문처리하면 됩니다.
✏️ 나의 풀이
#include <bits/stdc++.h>
using namespace std;
struct coord {
int y;
int x;
coord(int _y, int _x) : y(_y), x(_x) {}
coord operator-(coord c) {
return coord(x-c.x, y-c.y);
}
};
struct piece {
coord s; // 좌상단 좌표
coord e; // 좌하단 좌표
int num; // 조각 칸 수
bool isUsed; // 최종 계산 때, 조각 사용 여부를 저장하기 위함
vector<vector<int>> v;
piece(coord _s, coord _e) : s(_s), e(_e), num(0) {}
piece operator-(piece p) {
return piece(s-p.s, e-p.e);
}
// 조각의 가로, 세로 크기를 구하는 함수
pair<int,int> getShape() {
return make_pair(e.y-s.y+1, e.x-s.x+1);
}
// 조각의 모양이 같은가?
// (2,3)과 (3,2)도 같은 조각으로 친다.
bool isSameShape(piece p) {
coord d1 = e-s;
coord d2 = p.e-p.s;
if((d1.x == d2.x && d1.y == d2.y) || (d1.x == d2.y && d1.y == d2.x))
return true;
return false;
}
};
// 초반에 조각들을 분류하기 위한 DFS
void dfs(vector<vector<int>>& visited, vector<vector<int>>& table, coord cur, piece& rec, int pieceVal) {
if(cur.y < 0 || table.size() <= cur.y || cur.x < 0 || table[0].size() <= cur.x) return;
if(table[cur.y][cur.x] != pieceVal || visited[cur.y][cur.x]) return;
// 방문 처리
visited[cur.y][cur.x] = 1;
rec.num++;
rec.s.x = min(rec.s.x, cur.x);
rec.s.y = min(rec.s.y, cur.y);
rec.e.x = max(rec.e.x, cur.x);
rec.e.y = max(rec.e.y, cur.y);
// 상하
dfs(visited, table, coord(cur.y-1, cur.x), rec, pieceVal);
dfs(visited, table, coord(cur.y+1, cur.x), rec, pieceVal);
// 좌우
dfs(visited, table, coord(cur.y, cur.x-1), rec, pieceVal);
dfs(visited, table, coord(cur.y, cur.x+1), rec, pieceVal);
}
// 테이블에서 조각을 분류하고, 벡터에 담아 반환한다.
// game_board 배열과 table 배열 모두 이 함수를 사용한다.
vector<piece> get_pieces(vector<vector<int>>& table, int pieceVal) {
vector<vector<int>> visited(table.size(), vector<int>(table[0].size(), 0));
vector<piece> pieces;
for(int i=0; i<table.size(); i++) {
for(int j=0; j<table[i].size(); j++) {
piece rec = {coord(i,j), coord(i,j)};
if(table[i][j] == pieceVal && !visited[i][j]) {
dfs(visited, table, coord(i,j), rec, pieceVal);
pieces.push_back(rec);
}
}
}
for(int p=0; p<pieces.size(); p++) {
pair<int,int> shape = pieces[p].getShape();
pieces[p].v.resize(shape.first, vector<int>(shape.second, 0));
for(int i=0; i<shape.first; i++) {
for(int j=0; j<shape.second; j++) {
if(table[pieces[p].s.y+i][pieces[p].s.x+j] == pieceVal)
pieces[p].v[i][j] = 1;
}
}
}
return pieces;
}
// 90도 회전된 배열을 반환한다.
vector<vector<int>> rotatePiece(piece piece) {
vector<vector<int>> v = piece.v;
vector<vector<int>> ret(v[0].size(), vector<int>(v.size(), 0));
for(int i=0; i<v.size(); i++) {
for(int j=0; j<v[i].size(); j++) {
ret[j][v.size()-1-i] = v[i][j];
}
}
return ret;
}
// 조각을 끼울 수 있는지 판단하는 함수이다.
bool isMatch(piece gb_piece, piece tb_piece) {
if(!gb_piece.isSameShape(tb_piece)) return false;
for(int i=0; i<4; i++) {
tb_piece.v = rotatePiece(tb_piece);
if(gb_piece.v == tb_piece.v) return true;
}
return false;
}
int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
vector<piece> gb_pieces = get_pieces(game_board, 0);
vector<piece> tb_pieces = get_pieces(table, 1);
int cnt = 0;
for(int i=0; i<gb_pieces.size(); i++) {
for(int j=0; j<tb_pieces.size(); j++) {
// 조각이 사용된적 없으며, 조각을 끼울 수 있다면
if(!tb_pieces[j].isUsed && isMatch(gb_pieces[i], tb_pieces[j])) {
tb_pieces[j].isUsed = true;
cnt += gb_pieces[i].num;
break;
}
}
}
return cnt;
}
✔️ 다른 사람의 풀이
import java.util.ArrayList;
import java.util.Collections;
class Solution {
boolean[][] visited;
public int solution(int[][] game_board, int[][] table) {
int answer = 0;
// 퍼즐 조각을 담을 리스트.
ArrayList<ArrayList<String>> pieces = new ArrayList<>();
visited = new boolean[table.length][table[0].length];
// 테이블에서 퍼즐 조각을 탐색해 리스트에 담음.
for(int i = 0; i < table.length; i++){
for(int j = 0; j < table[0].length; j++){
if(table[i][j] == 1 && !visited[i][j]){
pieces.add(new ArrayList<>());
ArrayList<String> tmp = pieces.get(pieces.size()-1);
dfs(tmp, table, i, j, 0, 0, 1);
listSort(tmp);
}
}
}
// visited 초기화.
visited = new boolean[table.length][table[0].length];
for(int i = 0; i < game_board.length; i++){
for(int j = 0; j < game_board[0].length; j++){
// 게임보드에서 빈 칸 찾기.
if(game_board[i][j] == 0 && !visited[i][j]){
ArrayList<String> list = new ArrayList<>();
dfs(list, game_board, i, j, 0, 0, 0);
listSort(list);
// 조각들을 빈 칸에 맞춰 보는 과정.
for(int k = 0; k < pieces.size(); k++){
ArrayList<String> piece = pieces.get(k);
boolean isDone = false;
if(piece.size() != list.size()) continue;
for(int l = 0; l < 4; l++){
//System.out.println("빈칸 : " + list);
//System.out.println("퍼즐 조각 : " + piece);
//System.out.println();
// 빈 칸과 조각이 일치.
if(String.join(" ", piece).equals(String.join(" ", list))){
answer += list.size();
pieces.remove(k--);
// 일치한 조각은 리스트에서 삭제.
isDone = true;
break;
}
else{
//일치하지 않으면 조각을 회전.
rotate(piece);
//System.out.println("90도 회전");
}
}
if(isDone) break;
// 일치한 조각이 있다면 더 이상 새로운 조각을 맞춰보지 않음.
}
}
}
}
return answer;
}
// 빈 칸 및 퍼즐 조각 찾기.
void dfs(ArrayList<String> list, int[][] array, int i, int j, int x, int y, int n){
// 첫 블록(루트블록) 처리.
if(x == 0 && y == 0){
visited[i][j] = true;
list.add(x + " " + y);
}
// 상
if(i != array.length-1 && array[i+1][j] == n && !visited[i+1][j]){
visited[i+1][j] = true;
list.add(x + " " + (y+1));
dfs(list, array, i+1, j, x, y+1, n);
}
// 하
if(i != 0 && array[i-1][j] == n && !visited[i-1][j]){
visited[i-1][j] = true;
list.add(x + " " + (y-1));
dfs(list, array, i-1, j, x, y-1, n);
}
// 좌
if(j != 0 && array[i][j-1] == n && !visited[i][j-1]){
visited[i][j-1] = true;
list.add((x-1) + " " + y);
dfs(list, array, i, j-1, x-1, y, n);
}
// 우
if(j != array[0].length-1 && array[i][j+1] == n && !visited[i][j+1]){
visited[i][j+1] = true;
list.add((x+1) + " " + y);
dfs(list, array, i, j+1, x+1, y, n);
}
}
//퍼즐 조각 회전 (시계방향 90도)
void rotate(ArrayList<String> list){
for(int i = 0; i < list.size(); i++){
String str = list.get(i);
String[] splited = str.split(" ");
int x = Integer.parseInt(splited[0]);
int y = Integer.parseInt(splited[1]);
list.set(i, (y*-1) + " " + x);
// y를 음수로 변환 후, x와 y 반전.
}
listSort(list);
int x0 = 0;
int y0 = 0;
for(int i = 0; i < list.size(); i++){
String str = list.get(i);
String[] split = str.split(" ");
int x = Integer.parseInt(split[0]);
int y = Integer.parseInt(split[1]);
if(i == 0){ // 루트블록의 x와 y를 기록.
x0 = x;
y0 = y;
}
list.set(i, (x - x0) + " " + (y - y0));
// 모든 블록의 x와 y에 루트블록의 x, y를 뺌.
}
listSort(list);
}
// 루트블록이 list의 가장 앞에 오도록 하는 정렬.
void listSort(ArrayList<String> list){
list.sort((s1, s2) -> {
String[] split1 = s1.split(" ");
String[] split2 = s2.split(" ");
if (Integer.parseInt(split1[1]) == Integer.parseInt(split2[1]))
return Integer.parseInt(split1[0]) - Integer.parseInt(split2[0]);
return Integer.parseInt(split1[1]) - Integer.parseInt(split2[1]);
});
}
}
🧐 분석
- 배열을 사용하는 일반적인 풀이와는 다르게 문자열을 활용하고 있다.
- 다른 풀이도 많이 봤지만 기본적인 “퍼즐 조각 분류, 회전, 매칭” 이라는 큰 틀은 변하지 않았다.
🪶 후기
이번 문제는 DFS나 BFS처럼 알고리즘에 중점을 두기보단,
얼마나 구현을 잘 할수있는지 확인하는 문제였다.
어떻게 하면 최적화를 할 수 있을까?
탐색을 통해서만 풀순 없을까? 0과 1의 xor 연산을 통해 이진수로만 풀순 없을까? 와 같은 고민을 하다가 너무 많은 시간이 지나버렸다.
시간이 오래 걸린 이유에는 최적화 고민도 있고, 날씨가 더워짐으로써 컴퓨터 앞에 앉기가 힘들어지는 등 여러가지 이유가 있었다.
결국 너무 많은 시간이 걸려, 최적화보단 빨리 풀어보기로 했다.
여러모로 아쉬운 점이 많은 문제 풀이였다.
댓글남기기