Problem 문제풀이
내가 이렇게 실수가 많은 사람이라는 것을 알게 해준 문제이다.
1분을 빨리 풀려하다 1시간을 디버깅을 할 수 있다는 교훈을 주는 문제이다.
전략
-
초록색과 파란색 보드를 만든다.
-
주어진 좌표에서 블록을 떨어뜨린다.
-
한 행이 가득차게 되면 Clear하고 score을 1올린다.
-
만약 Clear했으면 Gravity를 주고 3. 을 실행한다.
-
더 Clear할 행이 없으면 Overflow를 검사한다.
-
Overflow가 일어났으면 전체 행을 한 줄씩 밑으로 내리고 5. 를 반복한다.
-
모든 블록을 떨어뜨렸으면 score와 남은 블록의 수를 출력한다.
이 문제는 계획을 잘 세우는 사람만 풀 수 있다. 무턱대고 덤비는 습관은 버리는 것이 좋다. (경험담임)
곰곰히 생각해보면 초록색 보드와 파란색 보드를 굳이 따로 만들 필요가 없다는 것을 알 수 있다.
int board[2][6][4]; // color, row, col
이제 떨어뜨린 블록을 보드에 채우는 함수를 만들어보자.
t가 1일 때는 한 칸짜리 블록이고 2는 초록색 기준으로 1*2
3은 초록색 기준으로 2*1 블록이다. 파란색은 xy대칭을 시켜서 넣으면 된다.
void Game(int _t, int _x, int _y)
{
if (_t == 1)
{
/* board[0] : 초록색
board[1] : 파란색 */
for (int i = 1; i < 6; i++)
{
if (board[0][i][_y] > 0)
{
board[0][i - 1][_y] = board_num;
break;
}
if (i == 5)
{
board[0][i][_y] = board_num;
}
}
for (int i = 1; i < 6; i++)
{
if (board[1][i][_x] > 0)
{
board[1][i - 1][_x] = board_num;
break;
}
if (i == 5)
{
board[1][i][_x] = board_num;
}
}
}
else if (_t == 2) // 초록색 기준 가로
{
/* board[0] : 초록색
board[1] : 파란색 */
for (int i = 1; i < 6; i++)
{
if (board[0][i][_y] > 0 || board[0][i][_y + 1] > 0)
{
board[0][i - 1][_y] = board_num;
board[0][i - 1][_y + 1] = board_num;
break;
}
if (i == 5)
{
board[0][i][_y] = board_num;
board[0][i][_y + 1] = board_num;
}
}
for (int i = 2; i < 6; i++)
{
if (board[1][i][_x] > 0)
{
board[1][i - 1][_x] = board_num;
board[1][i - 2][_x] = board_num;
break;
}
if (i == 5)
{
board[1][i - 1][_x] = board_num;
board[1][i][_x] = board_num;
}
}
}
else // 초록색 기준 세로
{
/* board[0] : 초록색
board[1] : 파란색 */
for (int i = 2; i < 6; i++)
{
if (board[0][i][_y] > 0)
{
board[0][i - 1][_y] = board_num;
board[0][i - 2][_y] = board_num;
break;
}
if (i == 5)
{
board[0][i - 1][_y] = board_num;
board[0][i][_y] = board_num;
}
}
for (int i = 1; i < 6; i++)
{
if (board[1][i][_x] > 0 || board[1][i][_x + 1] > 0)
{
board[1][i - 1][_x] = board_num;
board[1][i - 1][_x + 1] = board_num;
break;
}
if (i == 5)
{
board[1][i][_x] = board_num;
board[1][i][_x + 1] = board_num;
}
}
}
for (int c = 0; c < 2; c++)
{
Clear(c);
Overflow(c);
}
}
이렇게 넣는 작업까지는 5분이면 충분히 구현할 수 잇을 것이다. But! 오래 걸리더라도 실수 없이 하는 것이 제일 중요하다!
이제 Clear와 Overflow로 검사해보자. 먼저 Clear다.
void Clear(int color)
{
bool ret = false;
for (int i = 0; i < 6; i++)
{
ret = true;
for (int j = 0; j < 4; j++)
{
if (board[color][i][j] == 0)
{
ret = false;
break;
}
}
if (ret)
{
for (int j = 0; j < 4; j++)
{
board[color][i][j] = 0;
}
score++;
Gravity(color);
Clear(color);
}
}
}
한 행이 꽉 차있으면 그 줄을 Clear하고 Gravity를 준다.
이 문제에서 제일 실수가 많이 나올 수 있는 Gravity를 살펴보자.
void Gravity(int color)
{
bool ret = false;
for (int i = 4; i >= 0; i--)
{
for (int j = 0; j < 4; j++)
{
if (board[color][i][j] > 0 && board[color][i + 1][j] == 0)
{
if (j > 0 && board[color][i][j] == board[color][i][j - 1])
{
if (board[color][i + 1][j - 1] == 0)
{
board[color][i + 1][j] = board[color][i][j];
board[color][i + 1][j - 1] = board[color][i][j - 1];
board[color][i][j] = 0;
board[color][i][j - 1] = 0;
ret = true;
}
}
else if (j < 3 && board[color][i][j] == board[color][i][j + 1])
{
if (board[color][i + 1][j + 1] == 0)
{
board[color][i + 1][j] = board[color][i][j];
board[color][i + 1][j + 1] = board[color][i][j + 1];
board[color][i][j] = 0;
board[color][i][j + 1] = 0;
ret = true;
}
}
else
{
board[color][i + 1][j] = board[color][i][j];
board[color][i][j] = 0;
ret = true;
}
if (ret)
{
Gravity(color);
}
}
}
}
}
내 좌우에 있는 블록과 내가 같은 번호의 블록이고 둘 중에 하나라도 땅에 붙어있으면 Gravity가 작용하지 않는다.
둘 다 공중에 있거나 내 옆에 같은 번호의 블록이 없을 경우 낙하시키고 Gravity를 다시 부른다.
모든 블록이 땅에 붙으면 Gravity는 종료된다. 마지막으로 Overflow 함수를 살펴보자.
void Overflow(int color)
{
bool ret = false;
for (int i = 0; i < 4; i++)
{
if (board[color][1][i] > 0)
{
ret = true;
break;
}
}
if (ret)
{
for (int i = 5; i > 0; i--)
{
for (int j = 0; j < 4; j++)
{
board[color][i][j] = board[color][i - 1][j];
}
}
for (int i = 0; i < 4; i++)
{
board[color][0][i] = 0;
}
Overflow(color);
}
}
주의!! board[color][0]행을 0으로 초기화시키지 않으면 무한루프에 빠질 수 있다.
이 문제 푸는데 2시간은 넘게 사용했다. 실수를 줄이는 습관을 키우고 싶다면 이 문제를 꼭 풀어보기 바란다.
전체 코드를 남기며 마무리하겠다. Good Luck!
#include <iostream>
using namespace std;
int N, t, x, y, board_num, score, cnt;
int board[2][6][4]; // color, row, col
void Game(int _t, int _x, int _y);
void Count();
void Clear(int color);
void Gravity(int color);
void Overflow(int color);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> t >> x >> y;
board_num = i;
Game(t, x, y);
/*cout << '\n';
for (int j = 0; j < 6; j++)
{
for (int k = 0; k < 4; k++)
{
cout << board[0][j][k]<<' ';
}
cout << '\t';
for (int k = 0; k < 4; k++)
{
cout << board[1][j][3-k] << ' ';
}
cout << '\n';
}*/
}
Count();
cout << score << '\n' << cnt;
return 0;
}
void Game(int _t, int _x, int _y)
{
if (_t == 1)
{
/* board[0] : 초록색
board[1] : 파란색 */
for (int i = 1; i < 6; i++)
{
if (board[0][i][_y] > 0)
{
board[0][i - 1][_y] = board_num;
break;
}
if (i == 5)
{
board[0][i][_y] = board_num;
}
}
for (int i = 1; i < 6; i++)
{
if (board[1][i][_x] > 0)
{
board[1][i - 1][_x] = board_num;
break;
}
if (i == 5)
{
board[1][i][_x] = board_num;
}
}
}
else if (_t == 2) // 초록색 기준 가로
{
/* board[0] : 초록색
board[1] : 파란색 */
for (int i = 1; i < 6; i++)
{
if (board[0][i][_y] > 0 || board[0][i][_y + 1] > 0)
{
board[0][i - 1][_y] = board_num;
board[0][i - 1][_y + 1] = board_num;
break;
}
if (i == 5)
{
board[0][i][_y] = board_num;
board[0][i][_y + 1] = board_num;
}
}
for (int i = 2; i < 6; i++)
{
if (board[1][i][_x] > 0)
{
board[1][i - 1][_x] = board_num;
board[1][i - 2][_x] = board_num;
break;
}
if (i == 5)
{
board[1][i - 1][_x] = board_num;
board[1][i][_x] = board_num;
}
}
}
else // 파란색 기준 가로
{
/* board[0] : 초록색
board[1] : 파란색 */
for (int i = 2; i < 6; i++)
{
if (board[0][i][_y] > 0)
{
board[0][i - 1][_y] = board_num;
board[0][i - 2][_y] = board_num;
break;
}
if (i == 5)
{
board[0][i - 1][_y] = board_num;
board[0][i][_y] = board_num;
}
}
for (int i = 1; i < 6; i++)
{
if (board[1][i][_x] > 0 || board[1][i][_x + 1] > 0)
{
board[1][i - 1][_x] = board_num;
board[1][i - 1][_x + 1] = board_num;
break;
}
if (i == 5)
{
board[1][i][_x] = board_num;
board[1][i][_x + 1] = board_num;
}
}
}
for (int c = 0; c < 2; c++)
{
Clear(c);
Overflow(c);
}
}
void Clear(int color)
{
bool ret = false;
for (int i = 0; i < 6; i++)
{
ret = true;
for (int j = 0; j < 4; j++)
{
if (board[color][i][j] == 0)
{
ret = false;
break;
}
}
if (ret)
{
for (int j = 0; j < 4; j++)
{
board[color][i][j] = 0;
}
score++;
Gravity(color);
Clear(color);
}
}
}
void Gravity(int color)
{
bool ret = false;
for (int i = 4; i >= 0; i--)
{
for (int j = 0; j < 4; j++)
{
if (board[color][i][j] > 0 && board[color][i + 1][j] == 0)
{
if (j > 0 && board[color][i][j] == board[color][i][j - 1])
{
if (board[color][i + 1][j - 1] == 0)
{
board[color][i + 1][j] = board[color][i][j];
board[color][i + 1][j - 1] = board[color][i][j - 1];
board[color][i][j] = 0;
board[color][i][j - 1] = 0;
ret = true;
}
}
else if (j < 3 && board[color][i][j] == board[color][i][j + 1])
{
if (board[color][i + 1][j + 1] == 0)
{
board[color][i + 1][j] = board[color][i][j];
board[color][i + 1][j + 1] = board[color][i][j + 1];
board[color][i][j] = 0;
board[color][i][j + 1] = 0;
ret = true;
}
}
else
{
board[color][i + 1][j] = board[color][i][j];
board[color][i][j] = 0;
ret = true;
}
if (ret)
{
Gravity(color);
}
}
}
}
}
void Overflow(int color)
{
bool ret = false;
for (int i = 0; i < 4; i++)
{
if (board[color][1][i] > 0)
{
ret = true;
break;
}
}
if (ret)
{
for (int i = 5; i > 0; i--)
{
for (int j = 0; j < 4; j++)
{
board[color][i][j] = board[color][i - 1][j];
}
}
for (int i = 0; i < 4; i++)
{
board[color][0][i] = 0;
}
Overflow(color);
}
}
void Count()
{
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 4; j++)
{
if (board[0][i][j] > 0)
{
cnt++;
}
if (board[1][i][j] > 0)
{
cnt++;
}
}
}
}