출처 : 프로그래머스
난이도 : Level 3
문제 설명
문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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은 이미 채워진 칸을 나타냅니다.
- 퍼즐 조각이 놓일 빈칸은 1x1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
- table의 행 길이 = game_board의 행 길이
- table의 각 열 길이 = table의 행 길이
- 즉 , 테이블은 game_board의 행 길이
- table의 모든 원소는 0 또는 1입니다.
- 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
- 퍼즐 조각은 1x1 크기 정사각형이 최소 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 |
----------------------------------------------------------------------------------------------------------------------------
문제 해독
game_board에 빈칸에 table에 있는 블록들을 채워 넣습니다.
단 빈칸에 블록을 넣었을때 해당 인근에 빈칸이 있으면 안됩니다.
문제접근
game_board에서 빈칸을 블록 형태로 추출하고 table에서 꺼낸 블록과 길이 및 형태를 비교하여 채울 수 있는 칸수를 추출합니다.
필요 변수 리스트
- Point(블록의 좌표 클래스)
- boardBlocks(List<List<Point>> board의 빈칸 블록)
- tableBlocks(List<List<Point>> table의 빈칸 블록)
필요 알고리즘
- DFS
- 정규화
- 도형 회전
- 완전 탐색
- 그리디적 선택
- 시뮬레이션
using System;
using System.Collections.Generic;
public class Solution {
private int n;
private int m;
private int[] dx = {-1,1,0,0};
private int[] dy = {0,0,-1,1};
// 블록 좌표 클래스
class Point {
public int x;
public int y;
public Point(int x, int y) { this.x = x; this.y = y; }
public Point Clone() { return new Point(x, y); }
public bool Equals(Point other) { return x == other.x && y == other.y; }
}
public int solution(int[,] game_board, int[,] table) {
int answer = 0;
n = game_board.GetLength(0);
m = game_board.GetLength(1);
// 게임보드 빈칸 블록, 테이블 블록 추출
List<List<Point>> boardBlocks = GetBlocks(game_board, 0);
List<List<Point>> tableBlocks = GetBlocks(table, 1);
bool[] used = new bool[tableBlocks.Count];
// 게임보드 블록마다 테이블 블록 비교
foreach(var board in boardBlocks) {
for(int i = 0; i < tableBlocks.Count; i++) {
if(used[i]) continue;
if(board.Count != tableBlocks[i].Count) continue;
var rotations = GenerateRotations(tableBlocks[i]);
foreach(var block in rotations) {
if(IsSame(board, block)) {
answer += board.Count;
used[i] = true;
goto nextBoard;
}
}
}
nextBoard:;
}
return answer;
}
private List<List<Point>> GetBlocks(int[,] map, int target) {
bool[,] visited = new bool[n,m];
List<List<Point>> blocks = new List<List<Point>>();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!visited[i,j] && map[i,j] == target) {
List<Point> block = new List<Point>();
DFS(map, i, j, target, block, visited);
blocks.Add(Normalize(block));
}
}
}
return blocks;
}
private void DFS(int[,] map, int x, int y, int target, List<Point> block, bool[,] visited) {
visited[x,y] = true;
block.Add(new Point(x,y));
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(visited[nx,ny] || map[nx,ny] != target) continue;
DFS(map, nx, ny, target, block, visited);
}
}
private List<Point> Normalize(List<Point> block) {
int minX = int.MaxValue;
int minY = int.MaxValue;
foreach(var p in block) {
if(p.x < minX) minX = p.x;
if(p.y < minY) minY = p.y;
}
List<Point> normalized = new List<Point>();
foreach(var p in block) {
normalized.Add(new Point(p.x - minX, p.y - minY));
}
normalized.Sort((a,b) => {
int cmp = a.x.CompareTo(b.x);
return cmp != 0 ? cmp : a.y.CompareTo(b.y);
});
return normalized;
}
private List<List<Point>> GenerateRotations(List<Point> block) {
List<List<Point>> rotations = new List<List<Point>>();
List<Point> current = CloneBlock(block);
for(int i = 0; i < 4; i++) {
rotations.Add(CloneBlock(current));
current = RotateBlock(current);
}
return rotations;
}
private List<Point> RotateBlock(List<Point> block) {
List<Point> rotated = new List<Point>();
foreach(var p in block) {
rotated.Add(new Point(p.y, -p.x));
}
return Normalize(rotated);
}
private List<Point> CloneBlock(List<Point> block) {
List<Point> clone = new List<Point>();
foreach(var p in block) clone.Add(p.Clone());
return clone;
}
private bool IsSame(List<Point> a, List<Point> b) {
if(a.Count != b.Count) return false;
for(int i = 0; i < a.Count; i++) {
if(!a[i].Equals(b[i])) return false;
}
return true;
}
}