Programmers [2018 KAKAO BLIND RECRUITMENT]: [1차] 프렌즈4블록/BFS

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

코딩테스트 연습 - [1차] 프렌즈4블록

전형적인 좌표평면 문제이당

1️⃣블록 팝 2️⃣중력 이라는, 코딩테스트에 매우매우 자주 나오는 빈출 유형이기 때문에 반드시 여러 유형의 문제를 풀고, 코드를 외워놔야 한다

1️⃣블록 팝: 인접한 블록과 같다면 해당 블록을 팝 한다. 중요한 것은 이중 for문을 돌면서 실시간으로 pop을 해주면 안 되고, 팝 목록에 추가만 해줘야 한다

 해당 그림에서 좌표가 (1,0)일 때 인접한 네 칸을 pop한다면, 두 빨간 박스에 겹쳐 있는 오른쪽 아래 라이언도 없어지기 때문에 아래에 있는 박스는 제대로 pop할 수 없다

따라서 check배열을 선언해줘서, pop할 좌표들을 전부 체크해준 뒤 한꺼번에 pop한다

2️⃣중력: 해당 좌표들이 pop된 뒤, 위에 있는 블록들을 밑으로 전부 내려주는 작업이다. 이는 큐를 이용해서 의외로 간단하게 구현할 수 있다.

바로 모든 열에 대해 가장 아래 행부터 제일 위의 행까지 존재하는 블록을 모두 큐에 담은 뒤, 다시 아래부터 위의 순서로 체크하면서 큐에 있는 모든 원소를 빼주면 된다.

예를 들어 2열에서는 아래에서부터 (무지, 튜브, -, -, -, 튜브) 현재 이런 상태이다. 그러면 아래에서부터 큐에 담아 큐에는 (무지, 튜브, 튜브)가 담겨져있다. 다시 아래에서부터 순서대로 pop하면서 담아주면 (무지, 튜브, 튜브, -, -, -)가 된다.

이런 방식으로 중력 처리도 간단하게 구현할 수 있다.

모든 턴 마다 블록팝 - 중력을 계속 적용시켜 주면서, 블록팝이 일어나지 않을 때 까지 반복하면 끝 !

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
using namespace std;
string map[31];
bool check[31][31];
int dx[] = { 1,0,1,0 }, dy[] = { 1,1,0,0 };
int solution(int n, int m, vector<string> board) {
	int answer = 0;

	while (1) {
		bool B = true;
		memset(check, 0, sizeof(check));
		for (int i = 0; i < n - 1; i++)
			for (int j = 0; j < m - 1; j++) {
				char c = board[i][j];
				if (c=='0')continue;
				bool b = true;
				for (int k = 0; k < 3; k++)
					if (board[i + dy[k]][j + dx[k]] != board[i][j])
						b = false;
				if (b) {
					for (int k = 0; k < 4; k++)check[i + dy[k]][j + dx[k]] = 1;
					B = 0;
				}
			}
		for (int j = 0; j < m; j++) {
			queue<char> q;
			for (int i = n - 1; i >= 0; i--) {
				if (!check[i][j])q.push(board[i][j]);
				else answer++;
				board[i][j] = '0';
			}
			for (int i = n - 1; i >= 0; i--) {
				if (q.empty())break;
				board[i][j] = q.front(); q.pop();
			}
		}
		if (B)break;
	}
	return answer;
}