퍼즐 조각 채우기
[문제 Link] https://programmers.co.kr/learn/courses/30/lessons/84021
문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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
입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.
입출력 예 #2
블록의 회전은 가능하지만, 뒤집을 수는 없습니다.
로직
빈 칸이 0, 블록이 채워져 있는 공간이 1로 채워져 있고 보드를 채우기 위한 블록이 따로 주어진다. 이 때 블록을 최대한 많이 채울 경우의 채운 칸을 리턴하는 문제이다.
BFS를 통해 문제를 해결하였다.
-
BFS를 통해 보드 위의 빈 칸과 테이블의 블록들을 각각 list에 저장한다.
-
저장한 빈 칸과 블록들을 대조하여 최대로 빈 칸을 블록으로 채울 수 있는 방법을 찾는다.
전체 코드
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
class Solution
{
public static int[] dx = { -1, 0, 1, 0 };
public static int[] dy = { 0, 1, 0, -1 };
public static int solution(int[,] game_board, int[,] table)
{
int answer = -1;
bool[,] visitedTable = new bool[table.GetLength(0), table.GetLength(1)];
bool[,] visitedBoard = new bool[game_board.GetLength(0), game_board.GetLength(1)];
List<List<int[]>> boardList = new List<List<int[]>>();
List<List<int[]>> tableList = new List<List<int[]>>();
for (int i = 0; i < table.GetLength(0); i++)
{
for (int j = 0; j < table.GetLength(1); j++)
{
if (table[i, j] == 1 && !visitedTable[i, j])
{
bfs(i, j, visitedTable, table, 1, tableList);
}
if (game_board[i, j] == 0 && !visitedBoard[i, j])
{
bfs(i, j, visitedBoard, game_board, 0, boardList);
}
}
}
answer = findBlock(boardList, tableList);
return answer;
}
public static int findBlock(List<List<int[]>> board, List<List<int[]>> table)
{
int size = 0;
int tableLen = table.Count();
int boardLen = board.Count();
bool[] visitedBoard = new bool[boardLen];
for (int i = 0; i < tableLen; i++)
{
List<int[]> tablePoints = table[i];
for (int j = 0; j < boardLen; j++)
{
List<int[]> boardPoints = board[j];
if (tablePoints.Count() == boardPoints.Count() && !visitedBoard[j])
{ //좌표 개수 같을때
if (isRotate(boardPoints, tablePoints))
{ //회전해서 맞는지 확인
size += tablePoints.Count();
visitedBoard[j] = true;
break;
}
}
}
}
return size;
}
public static bool isRotate(List<int[]> board, List<int[]> table)
{
bool isCollect = false;
board.Sort((o1, o2) =>
{
return o1[0] > o2[0] ? 1 : o1[0] < o2[0] ? -1 : o1[1].CompareTo(o2[1]);
});
for (int i = 0; i < 4; i++)
{ //table퍼즐 0, 90, 180, 270도 회전
table.Sort((o1, o2) =>
{
return o1[0] > o2[0] ? 1 : o1[0] < o2[0] ? -1 : o1[1].CompareTo(o2[1]);
});
int nearZeroX = table[0][0];
int nearZeroY = table[0][1];
for (int j = 0; j < table.Count(); j++)
{
table[j][0] -= nearZeroX;
table[j][1] -= nearZeroY;
}
bool isCollectPoint = true;
for (int j = 0; j < board.Count(); j++)
{ //좌표 비교
int[] boardPoint = board[j];
int[] tablePoint = table[j];
if (boardPoint[0] != tablePoint[0] || boardPoint[1] != tablePoint[1])
{
isCollectPoint = false;
break;
}
}
if (isCollectPoint)
{
isCollect = true;
break;
}
else
{ //90도 회전 : x,y -> y, -x
for (int j = 0; j < table.Count(); j++)
{
int temp = table[j][0];
table[j][0] = table[j][1];
table[j][1] = -temp;
}
}
}
return isCollect;
}
public static void bfs(int currentX, int currentY, bool[,] visited, int[,] graph,int blockOrEmpty, List<List<int[]>> list)
{
Queue<int[]> queue = new Queue<int[]>();
visited[currentX, currentY] = true;
queue.Enqueue(new int[] { currentX, currentY });
List<int[]> subList = new List<int[]>();
subList.Add(new int[] { currentX - currentX, currentY - currentY });
while (queue.Count!=0)
{
int[] pop = queue.Dequeue();
int popX = pop[0];
int popY = pop[1];
for (int i = 0; i < 4; i++)
{
int nextX = popX + dx[i];
int nextY = popY + dy[i];
if (nextX < 0 || nextX >= graph.GetLength(0) || nextY < 0 || nextY >= graph.GetLength(0))
{
continue;
}
else
{
if (!visited[nextX, nextY] && graph[nextX, nextY] == blockOrEmpty)
{
visited[nextX, nextY] = true;
queue.Enqueue(new int[] { nextX, nextY });
subList.Add(new int[] { nextX - currentX, nextY - currentY });
}
}
}
}
list.Add(subList);
}
public static void Main(string[] args)
{
int[,] game_board = new int[,] { { 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[,] table = new int[,] { { 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 } };
Console.WriteLine(solution(game_board, table));
}
}
결과
