[문제]
블록게임
프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.
이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.
프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.
게임규칙
아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.
1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.
플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다.
이때, 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.
예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.
빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.
그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다.
따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.
보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.
제한사항
- board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.
- N은 4 이상 50 이하다.
- board의 각 행의 원소는 0 이상 200 이하의 자연수이다.
- 0 은 빈 칸을 나타낸다.
- board에 놓여있는 각 블록은 숫자를 이용해 표현한다.
- 잘못된 블록 모양이 주어지는 경우는 없다.
- 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
- 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.
입출력 예
| [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] |
[풀이]
1) 총 12가지의 블록이 생길 수 있는 데 블록의 모양대로 그려보니 위에서 부터 블록이 떨어져서 채워질 때 지워질 수 있는 블록의 모양은 5개로 추려졌다.
2) 블록의 모양에 관계없이 꽉 채워진 직사각형이 될 수 있는 블럭의 모양은 가로 * 세로가 3*2 혹은 2*3이다.
3) 즉, 6개의 블럭만 검사하면 된다. 검정색 블록이 채워야 할 공간은 2개이다. (2개가 넘어가는 순간 지워질 수 없는 블럭이다.)
4) 왼쪽 위부터 완탐을 하면서 6개씩 가로가 긴 직사각형 / 세로가 긴 직사각형을 만들어가면서 검사한다.
5) findBlocks()에는 파라미터로 현재 좌표와 가로가 긴 직사각형은 가로3 / 세로 2 를 주고
세로가 긴 직사각형은 가로2 / 세로 3을 준다.
직사각형은 보드의 크기를 넘어가면 안되기 때문에 가로가 긴 직사각형은 최대 n-3의 지점까지 직사각형을 만들 수 있다. (세로는 n-2)
세로가 긴 직사각형은 보드의 크기를 넘어가지 않으려면 n-3지점까지만 직사각형을 그려나가야 한다.
6) 지워질 수 있는 블록은 현재 위치를 기준으로 최상단 위치까지 모두 0으로 채워져 있어야 한다.
-> canMakeB 에서 검사한다.
7) 만약 현재 위치가 0이 아니고 블록이 있는 위치라면 그 블록의 넘버를 저장한다. (직사각형이 되는 블록은 블록의 번호가 모두 같아야 한다.) 만약 다르다면 그건 직사각형으로 형성될 수 없으므로 바로 함수를 빠져나온다.
**가지치기가 많다.. ㅜ
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> map;
bool canMakeB(int x, int y) {
//지금 위치를 기준으로 위쪽이 전부 0이어야 한다.
for (int i = 0; i < x; i++) {
if (map[i][y]) return false;
}
return true;
}
bool findBlocks(int x, int y, int h, int w) {
int empty_b = 0; //빈 공간은 최대 2개
int block_n = -1; //마지막으로 만난 블럭의, 번호 (직사각형을 구성하는 블럭의 번호는 모두 같아야 한다. )
for (int i = x; i < x + h; i++) {
for (int j = y; j < y + w; j++) {
if (!map[i][j]) {
if (!canMakeB(i, j)) {//직사각형이 될 수 있는 모형일 때 그 위에가 전부 0으로 채워져 있어야한다.
return false;
}
empty_b++;
if (empty_b > 2) return false;
}
else {
//0이 아닐 때
if (block_n != -1 && block_n != map[i][j]) {
//다른 번호의 블럭을 만남
return false;
}
block_n = map[i][j];
}
}
}
//지워질 수 있는 블럭이므로 지워준다.
for (int i = x; i < x + h; i++) {
for (int j = y; j < y + w; j++) {
map[i][j] = 0;
}
}
return true;
}
int solution(vector<vector<int>> board) {
int answer = 0;
//12가지 모양의 블럭 중 검정 블록을 떨어뜨려서 제거할 수 있는 모형은 5가지이다.
/*
1. ㄴ
2. ㄴ을 반시계 90도
3. 2번을 좌우대칭
4. 1번을 좌우 대칭
5. ㅗ
*/
//생길 수 있는 꽉 채워진 직사각형은 가로 세로가 2*3 / 3*2 이다.
//즉, 지금 위치에서 6개의 블럭들만 검사하면 된다.
//단, 예외처리를 해야할 부분은 직사각형이 될 수 있는 모형들이 공간의 띄우고 얽혀있는 경우이다.
//그렇기 때문에 만약, 검정 블럭이 들어가서 직사각형이 될 수있는 모형들은 그 모형을 기준으로 위쪽이 전부 0이어야 한다.
//검정 블럭으로 채워질 수 잇는 공간은 최대 2개이다.
//블럭들은 전부 번호가 같아야 하낟.
int n = board.size();
map = board;
int cnt ;
do{
cnt = 0;
//최초 한번은 탐색을 해야한다.
//지워질 블록이 1개라도 존재할 때 반복한다.
for (int i = 0;i <n; i++ ) {
for (int j = 0; j < n; j++) {
//총 6개의 블럭을 검사한다.
//가로가 3, 세로가 2인 블럭
if (i <= n-2 && j <= n-3 && findBlocks(i, j, 2, 3)) {
cnt++;
}
//가로가 2, 세로가 3인 블럭
else if (i <= n-3 && j <= n-2 &&findBlocks(i, j, 3, 2)) {
cnt++;
}
}
}
answer += cnt;
} while(cnt);
return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
[디버그 코드]
'Programmers > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 후보키 (0) | 2019.09.02 |
|---|---|
| [프로그래머스] 길찾기 게임 (0) | 2019.09.02 |
| [프로그래머스] 실패율 (0) | 2019.08.30 |
| [프로그래머스] 오픈채팅방 (0) | 2019.08.30 |
| [프로그래머스][1차] 다트게임 (0) | 2019.08.30 |
