[프로그래머스] 프렌즈4블록

2018 KAKAO BLIND RECRUITMENT [1차]

 

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록.
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

 

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

 

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

---

C++ 풀이

#include <string>
#include <vector>
#include <map>
using namespace std;

vector <vector <char>> b; //주어진 보드 블록 정보를 열단위로 저장
vector<vector <bool>> c; //제거할 블록 기록

int check(int x, int y) { //왼쪽 아래를 중심으로 2x2 사각형을 이루는지 체크
	char character = b[x][y];
	if (b[x + 1].size() <= y + 1) //오른쪽 위에 블록이 존재하는지 확인
		return 0;

	if ((b[x][y + 1] == character) && (b[x + 1][y] == character) && (b[x + 1][y + 1] == character)) { //4개의 블록이 같은 캐릭터라면
		int sum = 0;
		if (!c[x][y]) {
			sum++;
			c[x][y] = true;
		}
		if (!c[x + 1][y]) {
			sum++;
			c[x + 1][y] = true;
		}
		if (!c[x][y + 1]) {
			sum++;
			c[x][y + 1] = true;
		}
		if (!c[x + 1][y + 1]) {
			sum++;
			c[x + 1][y + 1] = true;
		}
		return sum;
	}
	else
		return 0;
}


int solution(int m, int n, vector<string> board) {
	int sum = 0;
	b.resize(n);
	c.resize(n);
	for (int i = m - 1; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			b[j].push_back(board[i][j]);
			c[j].push_back(false);
		}
	}
	int popN;
	do {
		popN = 0;
		for (int i = 0; i <= (int)b.size() - 2; i++) {
			for (int j = 0; j <= (int)b[i].size() - 2; j++)
				popN += check(i, j);
		}
		sum += popN;
		for (int k = 0; k < c.size(); k++) { //위 -> 아래 방향으로 블록을 지움
			for (int p = c[k].size() - 1; p >= 0; p--) {
				if (c[k][p]) {
					c[k][p] = false;
					b[k].erase(b[k].begin() + p);
				}
			}
		}
	} while (popN != 0); //더 이상 제거되는 블록이 없을때까지
	return sum;
}

벡터 범위를 잘 체크해주자.

 

 

 

 

 

 

 

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스