[C++] 백준 20061 모노미노도미노

문제 링크

---

www.acmicpc.net/problem/20061

20061번: 모노미노도미노 2

 

접근 방법

---

 한 보드에서 2점을 한번에 획득하는 경우를 충분히 고려하지 못하여 반례를 찾는데 시간이 좀 걸린 문제다.  

 

문제에 주어진 순서대로 구현을 하면된다.

1. 블럭 정보를 입력받는다.

2. 블럭 정보에 따라 파란보드와 초록보드에 표시한다.

3. 파란, 초록 보드를 각각 스캔하며 점수를 구하고 업데이트 한다.

 

1. 블럭 정보를 입력받는다 -> 블럭을 생성

vector<coord> constructor(int t, int x, int y) {

	vector<coord> block;

	if (t == 1)
		block.push_back({ x, y });
	else if (t == 2) {
		block.push_back({ x, y });
		block.push_back({ x, y + 1 });
	}
	else {
		block.push_back({ x, y });
		block.push_back({ x + 1, y });
	}
	return block;
}

 

2. 블럭 정보에 따라 각각의 보드에 표시한다.(파란 보드의 경우)

void moveToBlue(vector<coord> block) {

	bool ismove = true;

	while (ismove) {
		for (coord &elem : block) //이동
			elem.y += 1;
		for (coord elem : block) 
			if ( 9 < elem.y + 1 || mono[elem.x][elem.y + 1])
				ismove = false;
	}
	for (coord elem : block)
		mono[elem.x][elem.y] = true;
}

 

3. 보드를 각각 스캔하며 점수를 구하고 업데이트 한다.(blue board의 경우)

열이 꽉 차서 점수를 얻을 수 있을 때 열을 제거한 후 열을 가리키는 포인터를 유지해야 한다. 

int scanBlue() {

	int point = 0;

	for (int y = 9; y >= 6; y--) {
		int isFull = 0;
		for (int x = 0; x < 4; x++) {
			if (mono[x][y])
				isFull++;
		}
		if (isFull == 4) { //열이 꽉 찼다면
			deleteCol(y);  //열을 제거
			moveToBlueEnd(y); // 열의 오른쪽 부분을 왼쪽으로 모두 1칸 이동
			point++; //점수 증가
			y++;  // 제거 했다면 열을 가리키는 포인터를 유지시킴!! 
		}
	}

	for (int y = 4; y < 6; y++) {  // in Special Space
		for (int x = 0; x < 4; x++)
			if (mono[x][y]) {     //특별한 공간에 블럭이 포함됬다면
				deleteCol(9);     // 마지막 열 제거
				moveToBlueEnd(9);  // 마지막 열의 오른쪽 부분을 왼쪽으로 모두 1칸 이동
				break;
			}
	}
	return point;
}

 

3-1 deleteCol은 해당 열을 모두 지우는 함수이다.

void deleteCol(int col) {  //열
	for (int x = 0; x < 4; x++)
		mono[x][col] = false;
}

 

3-2 moveToBlueEnd(int col) -> col의 오른쪽 부분을 왼쪽으로 모두 1칸 이동시키는 함수 

void moveToBlueEnd(int col) {

	for (int y = col - 1; y > 3; y--) {
		for (int x = 0; x < 4; x++) {
			mono[x][y + 1] = mono[x][y];
			mono[x][y] = false;
		}
	}
}

 

 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct coord {
	int x, y;
};

bool mono[10][10];
int ans = 0;
int N;

vector<coord> constructor(int t, int x, int y) {

	vector<coord> block;

	if (t == 1)
		block.push_back({ x, y });
	else if (t == 2) {
		block.push_back({ x, y });
		block.push_back({ x, y + 1 });
	}
	else {
		block.push_back({ x, y });
		block.push_back({ x + 1, y });
	}
	return block;
}

void moveToBlue(vector<coord> block) {

	bool ismove = true;

	while (ismove) {
		for (coord &elem : block) //이동
			elem.y += 1;
		for (coord elem : block) 
			if ( 9 < elem.y + 1 || mono[elem.x][elem.y + 1])
				ismove = false;
	}
	for (coord elem : block)
		mono[elem.x][elem.y] = true;
}

void moveToGreen(vector<coord> block) {

	bool ismove = true;

	while (ismove) {
		for (coord &elem : block)
			elem.x += 1;
		for (coord elem : block)
			if ( 9 < elem.x + 1 || mono[elem.x + 1][elem.y])
				ismove = false;
	}
	for (coord elem : block)
		mono[elem.x][elem.y] = true;
}

void move(vector<coord> &block) {
	moveToGreen(block);
	moveToBlue(block);
}

void deleteRow(int row) {  //행
	for (int y = 0; y < 4; y++)
		mono[row][y] = false;
}

void deleteCol(int col) {  //열
	for (int x = 0; x < 4; x++)
		mono[x][col] = false;
}

void moveToBlueEnd(int col) {

	for (int y = col - 1; y > 3; y--) {
		for (int x = 0; x < 4; x++) {
			mono[x][y + 1] = mono[x][y];
			mono[x][y] = false;
		}
	}
}

void moveToGreenEnd(int row) {

	for (int x = row - 1; x > 3; x--) {
		for (int y = 0; y < 4; y++) {
			mono[x + 1][y] = mono[x][y];
			mono[x][y] = false;
		}
	}
}

int scanBlue() {

	int point = 0;

	for (int y = 9; y >= 6; y--) {
		int isFull = 0;
		for (int x = 0; x < 4; x++) {
			if (mono[x][y])
				isFull++;
		}
		if (isFull == 4) {
			deleteCol(y);
			moveToBlueEnd(y);
			point++;
			y++;
		}
	}

	for (int y = 4; y < 6; y++) {  // in Special Space
		for (int x = 0; x < 4; x++)
			if (mono[x][y]) {
				deleteCol(9);
				moveToBlueEnd(9);
				break;
			}
	}
	return point;
}

int scanGreen() {

	int point = 0;

	for (int x = 9; x >= 6; x--) {
		int isFull = 0;
		for (int y = 0; y < 4; y++) {
			if (mono[x][y])
				isFull++;
		}
		if (isFull == 4) {
			deleteRow(x);
			moveToGreenEnd(x);
			point++;
			x++;
		}
	}

	for (int x = 4; x < 6; x++) {  // in Special Space
		for (int y = 0; y < 4; y++)
			if (mono[x][y]) {
				deleteRow(9);
				moveToGreenEnd(9);
				break;
			}
	}
	return point;
}

int scan() {
	
	int point = 0;
	
	point += scanBlue();
	point += scanGreen();
	
	return point;
}

int solve() {

	int t, x, y, point;
	cin >> t >> x >> y;

	vector<coord> block = constructor(t, x, y);
	move(block);
	point = scan();

	return point;
}

int count() {

	int cnt = 0;

	for (int y = 6; y < 10; y++)
		for (int x = 0; x < 4; x++)
			if (mono[x][y])
				cnt++;

	for (int x = 6; x < 10; x++)
		for (int y = 0; y < 4; y++)
			if (mono[x][y])
				cnt++;

	return cnt;
}

int main() {

	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) 
		ans += solve();
		
	cout << ans << "\n";
	cout << count();
}

개발 환경 : VS2017

질문, 지적 환영합니다!