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

2018 카카오 블라인드 채용 1차 코딩테스트에서 나온 난이도는 상에 해당하는 문제이다.

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

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

처음에 이 문제를 봤을 때 그래프와 같은 표가 나와 그래프 자료구조(BFS,DFS)로 접근하려고 했었는데,

좀 더 생각해보니 지워야할 코드의 수는 2X2로 제한되어 있었기 때문에 간단한 반복문으로 해결 할 수 있는 문제였다.

 

 

이 문제에서 가장 신경 썼던 것은 위와 같이 모두 같은 2X2 블럭들을 지운 후 아래로 당겨지는 기능이었다.

처음에는 무작정 for문으로 해결하려 했지만  조금 복잡해져, Queue를 사용해 해결을 하는 방법으로 만들었다.

 

flush 메소드 - 블록들을 지운 후 아래로 당겨지게 해주는 메소드

vector<vector<char>> flush(vector<vector<char>> arr, int m, int n) {
	vector<vector<char>> tmp;
	tmp = vector<vector<char>>(m, vector<char>(n, 0));
	for (int i = 0; i < n; ++i) {
		queue<char> q;
		for (int j = m - 1; j >= 0; --j) {
			if (arr[j][i] != 0) {
				q.push(arr[j][i]);
			}
		}
		for (int j = m - 1; j >= 0; --j) {
			if (!q.empty()) {
				tmp[j][i] = q.front();
				q.pop();
			}
			else {
				tmp[j][i] = 0;
			}
		

		}
	}

	return tmp;
}

 

위 함수를 완성하고 블록들을 지워주는 함수를 만들었는데, 

m-1,n-1 블록까지 2X2 범위에 함수들을 하나하나 검사해 4개가 모두 같은 블록이면 해당 블록의 인덱스를 

vector<pair<int,int>> idxs 에 저장을 해준 후 idxs를 반복문을 통해 블록들을 지워주었다.

 

※여기에서 답을 위해 카운트를 증가시켜줘야 했는데, 그 블록이 0인 것을 감안해주는 조건문을 사용해줘야 한다.

 

소스 코드 :

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<pair<int,int>> block(vector<vector<char>> arr, int m, int n) {
	vector<pair<int, int>> tmp;

	for (int i = 0; i < m-1; i++) {
		for (int j = 0; j < n-1; ++j) {
			int eo = arr[i][j];
			if (eo!=0 && eo == arr[i][j + 1] && eo == arr[i + 1][j] && eo == arr[i + 1][j + 1]) {
				tmp.push_back(make_pair(i, j));
			}
		}
	}

	return tmp;
}

vector<vector<char>> flush(vector<vector<char>> arr, int m, int n) {
	vector<vector<char>> tmp;
	tmp = vector<vector<char>>(m, vector<char>(n, 0));
	for (int i = 0; i < n; ++i) {
		queue<char> q;
		for (int j = m - 1; j >= 0; --j) {
			if (arr[j][i] != 0) {
				q.push(arr[j][i]);
			}
		}
		for (int j = m - 1; j >= 0; --j) {
			if (!q.empty()) {
				tmp[j][i] = q.front();
				q.pop();
			}
			else {
				tmp[j][i] = 0;
			}
		

		}
	}

	return tmp;
}


int solution(int m, int n, vector<string> board) {
    int answer = 0;
    vector<vector<char>> arr;
	arr = vector<vector<char>>(m, vector<char>(n, 0));


	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			arr[i][j] = board[i][j];
		}
	}

	while (1) {
		vector<pair<int, int>> idxs = block(arr, m, n);
		if (idxs.size() == 0) {
			break;
		}
		for (int i = 0; i < idxs.size(); ++i) {
			int idx = idxs[i].first; int idy = idxs[i].second;
			if (arr[idx][idy] != 0) {
				answer++;
				arr[idx][idy] = 0;
			}
			if (arr[idx][idy + 1] != 0) {
				answer++;
				arr[idx][idy + 1] = 0;
			}
			if (arr[idx + 1][idy] != 0) {
				answer++;
				arr[idx + 1][idy] = 0;
			}
			if (arr[idx + 1][idy + 1] != 0) {
				answer++;
				arr[idx + 1][idy + 1] = 0;
			}

		}

		arr = flush(arr, m, n);
	}
    return answer;
}

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!