BOJ 20061 : 모노미노도미노 2 (삼성 SW TEST A형)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/20061

 

이후 설명 및 입/출력은 링크 참고

 

시뮬레이션 문제는 그대로 구현하면 되지만, 위 문제는 조금 복잡하다.

따라서 만들어야 하는 함수의 재활용을 잘 해야 구현과 디버깅이 쉽다.

 

먼저 전체 함수를 Blue / Green으로 나누는 것이 편하다.

 

1) block을 움직이는 함수는 moveBlue, moveGreen이다.

   block이 3가지 경우로 나뉘므로 내부에서 switch를 이용한다.

 

2) deleteBlue(column), deleteGreen(row) 함수로 블럭을 지운다.

 

3) getScoreBlue와 getScoreGreen 함수로 점수를 얻는다. 내부에서 deleteBlue/Green을 사용한다.

 

4) checkBlue와 checkGreen으로 특별한 칸에에 블럭이 있는지 체크하고, 블럭을 지운다.

   특별한 칸의 경우는 문제 링크에서 그림 7의 경우다.

---

모노미노도미노의 MAP은 RED, BLUE, GREEN으로 분리되어 있지만, 실제 구현은 MAP[11][11]로 정의한다.

따라서 BLUE와 GREEN의 START는 4, END는 9가 된다.

int MAP[11][11];

#define START (4)
#define END (9)

 

블럭을 움직일 때, 쉽게 멈추기 위해서 MAP의 끝 부분을 -1로 만들어둔다.

MAP[0][10] = MAP[1][10] = MAP[2][10] = MAP[3][10] = -1;
MAP[10][0] = MAP[10][1] = MAP[10][2] = MAP[10][3] = -1;

 

이번 문제에서는 input 없이, t, x, y (t, row, column)를 받으면서 MAP을 계속 갱신한다.

문제의 조건에서 score 계산을 먼저하라고 했기 때문에 block 제거로 score를 얻은 후에 특별한 칸을 처리한다.

int main(void)
{
	MAP[0][10] = MAP[1][10] = MAP[2][10] = MAP[3][10] = -1;
	MAP[10][0] = MAP[10][1] = MAP[10][2] = MAP[10][3] = -1;

	scanf("%d", &N);

	int score = 0;
	for (int i = 0; i < N; i++)
	{
		int t, r, c;
		
		scanf("%d %d %d", &t, &r, &c);
		
        /* block 이동 */
		moveBlue(t, r, c);
		moveGreen(t, r, c);
		
		/* score 계산 */
        
 		/* 특별한 칸 처리 */
	}
    
    ...
    
    return 0;
}

 

moveBlue는 아래와 같이 구성된다. Green에 대한 모든 함수는 전체 코드를 참고하자.

void moveBlue(int t, int sr, int sc)
{
	int c;

	switch (t)
	{
	case 1:

		for (c = sc; ; c++)
			if (MAP[sr][c + 1] != 0) break;

		MAP[sr][c] = 1;

		break;
	case 2:

		for (c = sc; ; c++)
			if (MAP[sr][c + 2] != 0) break;
		
		MAP[sr][c] = MAP[sr][c + 1] = 1;

		break;
	case 3:
		
		for (c = sc; ; c++)
		{
			if (MAP[sr][c + 1] != 0) break;
			if (MAP[sr + 1][c + 1] != 0) break;
		}

		MAP[sr][c] = MAP[sr + 1][c] = 1;

		break;
	default:
		break;
	}
}

 

블럭이 1 x 1인 경우는 c + 1을 check하여 움직일 수 있는 최대 column을 찾는다.

최대 column을 찾으면 MAP[sr][c] = 1로 check한다.

 

블럭이 1 x 2인 경우는 c + 2를 check해야하고,

블럭이 2 x 1인 경우는 블럭의 row와 row + 1 모두 check해야 한다.

두 경우 모두 check가 완료되면 MAP에 block을 표시한다.

---

deleteBlue는 아래와 같이 구현한다.

특정 column을 기준으로 왼쪽에서 오른쪽으로 한 칸 당긴다.

그리고 마지막 START에 해당하는 MAP을 모두 0으로 만들어야 남아있는 block이 까지 움직이게 된다.

void deleteBlue(int column)
{
	for (int c = column; c > START; c--)
		for (int r = 0; r < 4; r++)
			MAP[r][c] = MAP[r][c - 1];

	MAP[0][START] = MAP[1][START] = MAP[2][START] = MAP[3][START] = 0;
}

 

이렇게 만들어 두면, block이 4칸이 모인 곳을 넘겨주기만 하면 블럭이 한 칸 옆으로 움직이게 되고,

특별한 칸에 블럭이 있는 경우는 deleteBlue(END)를 해주면 된다. 

 

getScoreBlue는 모든 column을 조사해서 cnt가 4가 되는지 확인하고,

4가 된다면 해당 칸을 지우고 return 1을 해서 점수를 반환한다.

int getScoreBlue()
{
	for (int c = START; c <= END; c++)
	{
		int cnt = 0;
		
		for (int r = 0; r < 4; r++) cnt += MAP[r][c];

		if (cnt == 4)
		{
			deleteBlue(c);
			return 1;
		}
	}

	return 0;
}

 

block은 한 번에 최대 2번 지워지기 때문에, 위 함수를 2번 호출하는 것으로 충분하다.

block이 최대 2번 지워지는지 check하여 한 번에 2번 지울 수도 있지만, 

MAP이 워낙 작아 비용이 많이 들지 않고, 구현량이 늘어나면 디버깅만 더 어려워질 뿐이다.

for (int i = 0; i < N; i++)
{
	int t, r, c;
		
	scanf("%d %d %d", &t, &r, &c);

	/* block 이동 */
    ...
    
    /* score 계산 */
	score += getScoreBlue();
	score += getScoreBlue();

	score += getScoreGreen();
	score += getScoreGreen();

	
}

---

checkBlue는 특별한 칸에 block이 있는지 확인한다. 

START에 block이 있다는 것은 START + 1에도 반드시 block이 있으므로, START + 1만 검사한다.

int checkBlue()
{
	for (int r = 0; r < 4; r++)
		if (MAP[r][START + 1]) return 1;

	return 0;
}

 

마찬가지로, 특별한 칸도 2개가 연속으로 있을 수 있으므로 2번 호출하면 된다.

그리고 특별한 칸에 block이 있는 경우는 모든 block이 한 칸씩 밀리므로 deleteBlue(END)를 호출한다.

for (int i = 0; i < N; i++)
{
	int t, r, c;
		
	scanf("%d %d %d", &t, &r, &c);

	/* block 이동 */
	...
    
	/* score 계산 */
	...
    
	/* 특별한 칸 처리 */
	if (checkBlue()) deleteBlue(END);
	if (checkBlue()) deleteBlue(END);

	if (checkGreen()) deleteGreen(END);
	if (checkGreen()) deleteGreen(END);
}

 

마지막으로 남아있는 칸의 수를 세면 구현은 완료된다.

Green부분과 함께 전체 코드를 확인하자.

#include <stdio.h>

int N;
int MAP[11][11];

#define START (4)
#define END (9)

void output()
{
	for (int r = 0; r < 11; r++)
	{
		for (int c = 0; c < 11; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void moveBlue(int t, int sr, int sc)
{
	int c;

	switch (t)
	{
	case 1:

		for (c = sc; ; c++)
			if (MAP[sr][c + 1] != 0) break;

		MAP[sr][c] = 1;

		break;
	case 2:

		for (c = sc; ; c++)
			if (MAP[sr][c + 2] != 0) break;
		
		MAP[sr][c] = MAP[sr][c + 1] = 1;

		break;
	case 3:
		
		for (c = sc; ; c++)
		{
			if (MAP[sr][c + 1] != 0) break;
			if (MAP[sr + 1][c + 1] != 0) break;
		}

		MAP[sr][c] = MAP[sr + 1][c] = 1;

		break;
	default:
		break;
	}
}

void moveGreen(int t, int sr, int sc)
{
	int r;

	switch (t)
	{
	case 1:

		for (r = sr; ; r++)
			if (MAP[r + 1][sc] != 0) break;

		MAP[r][sc] = 1;

		break;
	case 2:

		for (r = sr; ; r++)
		{
			if (MAP[r + 1][sc] != 0) break;
			if (MAP[r + 1][sc + 1] != 0) break;
		}

		MAP[r][sc] = MAP[r][sc + 1] = 1;
		break;
	case 3:

		for (r = sr; ; r++)
			if (MAP[r + 2][sc] != 0) break;

		MAP[r][sc] = MAP[r + 1][sc] = 1;

		break;
	default:
		break;
	}
}

void deleteBlue(int column)
{
	for (int c = column; c > START; c--)
		for (int r = 0; r < 4; r++)
			MAP[r][c] = MAP[r][c - 1];

	MAP[0][START] = MAP[1][START] = MAP[2][START] = MAP[3][START] = 0;
}

void deleteGreen(int row)
{
	for (int r = row; r > START; r--)
		for (int c = 0; c < 4; c++)
			MAP[r][c] = MAP[r - 1][c];

	MAP[START][0] = MAP[START][1] = MAP[START][2] = MAP[START][3] = 0;
}

int getScoreBlue()
{
	for (int c = START; c <= END; c++)
	{
		int cnt = 0;
		
		for (int r = 0; r < 4; r++) cnt += MAP[r][c];

		if (cnt == 4)
		{
			deleteBlue(c);
			return 1;
		}
	}

	return 0;
}

int getScoreGreen()
{
	for (int r = START; r <= END; r++)
	{
		int cnt = 0;
		for (int c = 0; c < 4; c++) cnt += MAP[r][c];

		if (cnt == 4)
		{
			deleteGreen(r);
			return 1;
		}
	}

	return 0;
}

int checkBlue()
{
	for (int r = 0; r < 4; r++)
		if (MAP[r][START + 1]) return 1;

	return 0;
}

int checkGreen()
{
	for (int c = 0; c < 4; c++)
		if (MAP[START + 1][c]) return 1;

	return 0;
}

int main(void)
{
	MAP[0][10] = MAP[1][10] = MAP[2][10] = MAP[3][10] = -1;
	MAP[10][0] = MAP[10][1] = MAP[10][2] = MAP[10][3] = -1;

	scanf("%d", &N);

	int score = 0;
	for (int i = 0; i < N; i++)
	{
		int t, r, c;
		
		scanf("%d %d %d", &t, &r, &c);

		/* block 이동 */
		moveBlue(t, r, c);
		moveGreen(t, r, c);
		
		/* score 계산 */
		score += getScoreBlue();
		score += getScoreBlue();

		score += getScoreGreen();
		score += getScoreGreen();

		/* 특별한 칸 처리 */
		if (checkBlue()) deleteBlue(END);
		if (checkBlue()) deleteBlue(END);

		if (checkGreen()) deleteGreen(END);
		if (checkGreen()) deleteGreen(END);
	}

	int blockCount = 0;
	
	for (int r = START; r <= END; r++)
		for (int c = 0; c < 4; c++) blockCount += MAP[r][c];

	for (int c = START; c <= END; c++)
		for (int r = 0; r < 4; r++) blockCount += MAP[r][c];

	printf("%d\n%d\n", score, blockCount);

	return 0;
}

 

실제 A형은 tc가 여러 개이므로 MAP에 남아있는 block을 모두 초기화하는 코드를 추가해야 한다.