문제 출처

1. 문제설명

  • 아래 그림과 같은 테트리스 그림판이 주어진다.

  • 놓을 수 있는 블록의 종류는 총 3가지이다.

  • 블록을 놓으면 동시에 파란색, 초록색 영역으로 이동한다.
    • 파란색 영역의 맨 끝 열로 이동한다.(행은 같다.)
    • 초록색 영역의 맨 끝 행으로 이동한다.(열은 같다.)
  • 파란색 영역의 한 열이 가득차면 터지고, 그 이전 열은 한칸씩 오른쪽으로 이동한다.
  • 초록색 영역의 한 행이 가득차면 터지고, 그 이전 행은 한칸씩 아래쪽으로 이동한다.
  • 파란색과 초록색 영역의 연한 칸(0~1번째)은 특별한 영역이다.
    • 해당 부분에 블록이 생기는 경우 칸수만큼 끝으로 이동하고, 맵밖을 벗어난 블록은 지워진다.
  • 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리


2. 입/출력

  • 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)
  • N개의 줄에 블록을 놓은 정보 t x y와 같은 형태이다.
    • t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
    • t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
    • t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우

  • 블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.

  • 첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.
  • 둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.


3. 문제 분류

  • Simulation


4. 알고리즘 설계

  • 블록을 쌓을 때마다 언급된 과정이 진행되어야 한다.
  • 프로세스
    • 새로운 블록의 정보를 입력받는다.
    • 파란색, 초록색 영역 블록 이동
    • 파란색, 초록색 영역 블록 터트리기
    • (터트린 게 있다면) 블록 이동
    • 특별한 칸의 영역 이동
  • 참고로 파란색, 초록색 영역은 별개이므로 무엇을 먼저 수행해도 상관없다.

  • 별개의 영역이기 때문에 파란색, 초록색 영역을 별도의 배열로 선언하였다.

  • 블록의 이동(move)

    • 블록의 이동은 1, 2, 3번 블록을 처리하기 위해 다음 배열을 선언하였다.

      const int dx[] = { 0, 0, 0, 1 };
const int dy[] = { 0, 0, 1, 0 };

    • 1번 블록은 한칸이고 2, 3번 블록은 오른쪽 또는 아래쪽으로 확장한 형태이다.

      • 그래서 dx[0], dy[0]을 더한다고 해도 같은 값이다.
      vector<pii> pos;
pos.push_back({ cx, 0 });
pos.push_back({ cx + dx[t], 0 + dy[t] });
      • 위와 같이 벡터에 넣고 지정 방향으로 움직이면서 블록을 만나거나 oom이 되면 멈추게 만들었다.
  • 블록 터트리기(pop)
    • 영역의 한 줄이 가득차면 터트려야 한다.
    • 해당 영역의 값을 -1로 만들고, drop()이라는 함수에서 처리하였다.
  • 블록 떨어뜨리기(drop)
    • 0번째 값이 -1이란 것은 한 행이 전부 -1이란 의미이다.
      • 한줄이 가득 차야 터지고 그때 -1로 표시했기 때문
    • -1인 값을 0으로 바꾸고 해당 칸은 그 옆 칸의 값으로 바꿔주었다.
      • shift를 한 느낌이다.
      • 0으로 바꾼 이유는 당겨졌을 때 새로운 칸은 0으로 채워지기 때문이다.
  • 특별한 영역(special)
    • 특별한 영역도 pop과 다르지 않다.
    • 해당 영역의 값을 -1로 만든다.
    • 이후 drop 함수를 호출하여 이동시켜준다.


5. 전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
using pii = pair<int, int>;

const int dx[] = { 0, 0, 0, 1 };
const int dy[] = { 0, 0, 1, 0 };

int blue[4][6], green[6][4];
int k, t, cx, cy;
int score;

bool oom(int p) { return p < 0 || p >= 6; }

void move_blue() {
	vector<pii> pos;
	pos.push_back({ cx, 0 });
	pos.push_back({ cx + dx[t], 0 + dy[t] });

	bool flag = true;
	while (flag) {
		for (auto& nxt : pos) {
			int ny = nxt.Y + 1;
			if (ny >= 6 || blue[nxt.X][ny] != 0) {
				flag = false;
				break;
			}
		}

		if (flag) {
			pos[0].Y += 1;
			pos[1].Y += 1;
		}
	}

	for (auto& nxt : pos)
		blue[nxt.X][nxt.Y] = 1;
}

void move_green() {
	vector<pii> pos;
	pos.push_back({ 0, cy });
	pos.push_back({ 0 + dx[t], cy + dy[t] });

	bool flag = true;
	while (flag) {
		for (auto& nxt : pos) {
			int nx = nxt.X + 1;
			if (nx >= 6 || green[nx][nxt.Y] != 0) {
				flag = false;
				break;
			}
		}

		if (flag) {
			pos[0].X += 1;
			pos[1].X += 1;
		}
	}

	for (auto& nxt : pos)
		green[nxt.X][nxt.Y] = 1;
}

bool pop_blue() {
	bool ret = false;

	for (int j = 0; j < 6; j++) {
		bool flag = true;
		for (int i = 0; i < 4; i++)
			if (blue[i][j] == 0) flag = false;

		if (flag) {
			ret = true;
			for (int i = 0; i < 4; i++) blue[i][j] = -1;
			score++;
		}
	}

	return ret;
}

bool pop_green() {
	bool ret = false;

	for (int i = 0; i < 6; i++) {
		bool flag = true;
		for (int j = 0; j < 4; j++)
			if (green[i][j] == 0) flag = false;

		if (flag) {
			ret = true;
			for (int j = 0; j < 4; j++) green[i][j] = -1;
			score++;
		}
	}

	return ret;
}

void drop_blue() {
	for (int j = 5; j > 0; j--) {
		if (blue[0][j] == -1) {
			for (int i = 0; i < 4; i++) blue[i][j] = 0;

			for (int k = j - 1; k >= 0; k--)
				for (int i = 0; i < 4; i++) blue[i][k + 1] = blue[i][k];

			for (int i = 0; i < 4; i++) blue[i][0] = 0;

			j++;
		}
	}
	for (int j = 5; j >= 0; j--)
		if (blue[0][j] == -1)
			for (int i = 0; i < 4; i++) blue[i][j] = 0;
}

void drop_green()  {
	for (int i = 5; i > 0; i--) {
		if (green[i][0] == -1) {
			for (int j = 0; j < 4; j++) green[i][j] = 0;

			for (int k = i - 1; k >= 0; k--)
				for (int j = 0; j < 4; j++) green[k + 1][j] = green[k][j];

			for (int j = 0; j < 4; j++) green[0][j] = 0;

			i++;
		}
	}

	for (int i = 5; i >= 0; i--)
		if (green[i][0] == -1)
			for (int j = 0; j < 4; j++) green[i][j] = 0;
}

void drop_special_blue() {
	int cnt = 0;

	for (int j = 0; j < 2; j++) {
		bool flag = false;

		for (int i = 0; i < 4; i++) {
			if (blue[i][j] != 0) {
				flag = true;
				break;
			}
		}

		if (flag) cnt++;
	}

	for (int j = 5; j > 5 - cnt; j--)
		for (int i = 0; i < 4; i++)
			blue[i][j] = -1;
}

void drop_special_green() {
	int cnt = 0;

	for (int i = 0; i < 2; i++) {
		bool flag = false;

		for (int j = 0; j < 4; j++) {
			if (green[i][j] != 0) {
				flag = true;
				break;
			}
		}

		if (flag) cnt++;
	}

	for (int i = 5; i > 5 - cnt; i--)
		for (int j = 0; j < 4; j++)
			green[i][j] = -1;
}

int count() {
	int cnt = 0;

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 6; j++)
			cnt += blue[i][j] > 0;
	for (int i = 0; i < 6; i++)
		for (int j = 0; j < 4; j++)
			cnt += green[i][j] > 0;

	return cnt;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	//freopen("input.txt", "r", stdin);

	cin >> k;
	while (k--) {
		cin >> t >> cx >> cy;

		move_blue();
		move_green();

		if (pop_blue()) drop_blue();
		if (pop_green()) drop_green();

		drop_special_blue();
		drop_blue();
		drop_special_green();
		drop_green();
	}

	cout << score << '\n' << count();

	return 0;
}


4. 소감

  • 파란색, 초록색 영역의 가로 세로 길이가 달라서 함수를 전부 별도 구현하였다.
  • 그래도 drop 함수를 재사용 한 것은 괜찮았던 거 같다.
  • 이 문제를 풀 때 -1 처리에서 새로운 영역을 0으로 처리하지 않아 많이 헤맷던 거 같다.
  • 디버깅을 통해서 해결했지만, 실제 코딩테스트에서는 디버거가 없는 경우가 많으므로 머리나 종이에 로직을 시뮬레이션해서 수정하는 연습을 많이 해봐야겠다고 느꼈다.