[Programmers] Lv2. 프렌즈4블록

• 이 문제는 C++로 풀이를 작성하였습니다.

풀이

	#include <string>
	#include <vector>
	#include <queue>
	#include <utility>
	using namespace std;
	int dir[3][2]={{1,0},{0,1},{1,1}};
	// 좌표안에 있는지 확인하는 함수
	bool inside(int m,int n,int y,int x, vector<string>& board){
	char op=board[y][x];
	for(int i=0;i<3;i++){
	int dy=y+dir[i][0];
	int dx=x+dir[i][1];
	if(dy>=m || dx>=n || op!=board[dy][dx]){
	return false;
	}
	}
	return true;
	}
	// 한 좌표씩 확인하여 bfs로 지워지는 조건이 있는지 확인
	// 방문한 노드는 다시 방문하지 않는다
	// 한번이라도 지워진다면 다시 처음부터 실행
	int solution(int m, int n, vector<string> board) {
	int answer = 0;
	bool flag=true;
	// flag는 변동이 있는지 확인하는 변수
	while(flag){
	flag=false; // flase로 한 후 변동이 있으면 true
	bool check[50][50]={0};
	bool change[50][50]={0};
	// bfs로 방문, 방문한 노드는 다시 방문하지 않는다
	for(int i=0;i<m;i++){
	for(int j=0;j<n;j++){
	if(check[i][j]==0 && board[i][j]!='X'){
	queue<pair<int,int>> q;
	q.push(make_pair(i,j));
	bool find=false;
	while(!q.empty()){
	int ty=q.front().first;
	int tx=q.front().second;
	q.pop();
	check[ty][tx]=1;
	if(inside(m,n,ty,tx,board)){
	board[ty][tx]='X';
	if(change[ty][tx]==0){
	answer++;
	change[ty][tx]=1;
	}
	find=true;
	flag=true;
	for(int k=0;k<3;k++){
	q.push(make_pair(ty+dir[k][0],tx+dir[k][1]));
	}
	}
	if(find){
	board[ty][tx]='X';
	if(change[ty][tx]==0){
	answer++;
	change[ty][tx]=1;
	}
	}
	}
	}
	}
	}
	// X를 아래로 내리는 작업
	for(int i=0;i<n;i++){
	string temp="";
	for(int j=0;j<m;j++){
	if(board[j][i]=='X'){
	temp=board[j][i]+temp;
	}
	else{
	temp+=board[j][i];
	}
	}
	for(int j=0;j<m;j++){
	board[j][i]=temp[j];
	}
	}
	}
	return answer;
	}

view raw Programmers Lv2. friends 4 block.cpp hosted with ❤ by GitHub

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.