[카카오] 2018블라인드채용 - 7번 문제(블록 게임)

출처 :

'19 카카오 코딩 테스트 (C++) - YouTube

문제

 

블록게임

프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.

이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.

프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.

 

게임규칙

아래 그림과 같이 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에 놓여있는 각 블록은 숫자를 이용해 표현한다.
• 잘못된 블록 모양이 주어지는 경우는 없다.
• 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
• 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

 

입출력 예

board	result
[[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]]	2

 

 

풀이과정

 

1.규칙

• 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.
• 플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다.
• board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.
• 0 은 빈 칸을 나타낸다.
• 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.

 

2.순서

 

(1)직사각형 체크

3종류의 블록으로 만들 수 있는 직사각형은 3X2, 2X3 뿐이므로 (0,0) 위치부터 두 직사각형을 만들 수 있는지 체크합니다.

 

 

이때, 빈칸이 3개 이상일 경우 또는 직사각형 안에 다른 번호의 블록이 들어오는 경우는 깨질 수 없는 블록이므로 유의합니다.

 

(2)블록은 위에서 떨어짐

 

 

블록은 맨 위에서 떨어져 블록위에 쌓여야 하므로 (0,j)부터 (i-1,j)까지 블록이 있는지 없는지 체크합니다.

 

(3)NxN 영역 안에서만 검사

 

 

직사각형 검사는 NxN 안에서만 체크해야 함을 유의합니다.

 

 

3.코드

 

	#include <vector>
	using namespace std;
	int N;
	vector<vector<int>> Board;
	//블록 떨어트릴수 있는가?
	bool canFill(int row, int col)
	{
	for (int i = 0; i < row; i++)
	if (Board[i][col] != 0) return false;
	return true;
	}
	//지울수 있는 블록을 찾는다
	bool find(int row, int col, int h, int w)
	{
	int emptyCnt = 0;
	int lastValue = -1;
	for (int i = row; i < row + h; i++)
	{
	for (int j = col; j < col + w; j++)
	{
	if (Board[i][j] == 0){
	if (!canFill(i, j)) return false;
	if (++emptyCnt > 2) return false;
	}
	else{
	//직사각형안에 다른번호의 블록이 들어갈 경우
	if (lastValue != -1 && lastValue != Board[i][j]) return false;
	lastValue = Board[i][j];
	}
	}
	}
	//영역 지우기
	for (int i = row; i < row + h; i++)
	for (int j = col; j < col + w; j++)
	Board[i][j] = 0;
	return true;
	}
	int solution(vector<vector<int>> board) {
	Board = board;
	N = board.size();
	int answer = 0, cnt;
	do {
	cnt = 0;
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < N; j++)
	{
	if (i <= N - 3 && j <= N - 2 && find(i, j, 3, 2)) cnt++;//3X2직사각형
	else if (i <= N - 2 && j <= N - 3 && find(i, j, 2, 3)) cnt++;//2X3직사각형
	}
	}
	answer += cnt;
	} while (cnt);
	return answer;
	}

view raw 공채1차_7번문제_블록 게임.cpp hosted with ❤ by GitHub