백준 25209 - 샤카샤카(C++)

문제 링크입니다. 

https://www.acmicpc.net/problem/25209

25209번: 샤카샤카

구현할 것이 많은 문제였습니다.

 

주어진 블럭이 조건에 맞는지를 확인하는 문제입니다.

조건은 2가지입니다.

1. 연속한 흰색 부분은 직사각형이여야 한다.

2. 숫자 K가 적힌 정사각형의 상하좌우에는 삼각형 블록이 K개 있어야한다.

 

문제를 풀기전에 주어진 map이 복잡하기에 단순하게 바꾸겠습니다.

블럭들을 순서대로 1~6번이라고 정하겠습니다.

해당 블럭과 같이 사이에 숫자가 있는 경우, 가운데 숫자를 기준으로 블럭을 저장합니다.

저는 -0, -1, -2와 같이 '-'를 곱해서 저장해줬습니다.

char blocks[6][3][3] = {
	{{'.','.','.'}, {'.','.','.'}, {'.','.','.'}},
	{{'#','#','#'}, {'#','#','#'}, {'#','#','#'}},
	{{'#','.','.'}, {'#','#','.'}, {'#','#','#'}},
	{{'#','#','#'}, {'.','#','#'}, {'.','.','#'}},
	{{'#','#','#'}, {'#','#','.'}, {'#','.','.'}},
	{{'.','.','#'}, {'.','#','#'}, {'#','#','#'}}
};

void Remake(int x, int y) {
	for (int k = 0; k < 6; k++) {
		int Same = 0;
		for (int i = 1; i <= 3; i++) {
			for (int j = 1; j <= 3; j++) {
				if (map[i + (x - 1) * 3][j + (y - 1) * 3] == blocks[k][i - 1][j - 1]) Same++;
			}
		}
		if (Same == 9) {
			remake_map[x][y] = k + 1;
			return;
		}
	}
	remake_map[x][y] = -(map[2 + (x - 1) * 3][2 + (y - 1) * 3] - '0');
}

 

첫번째 조건은 K가 써있는 블럭의 상하좌우에 K개의 블럭이 있어야합니다.

앞에서 해당 블럭은 '-'가 붙여서 저장되어 있으니 해당 블럭을 찾은 뒤 4방향만 확인해주면 됩니다.

 

두번째 조건은 흰색 부분이 전부 직사각형으로 이루어져야 합니다.

직사각형이 만들어질 수 있는 조건은 2개가 있습니다.

1. 윗쪽에는 5번 + 4번 블럭이 이어져있고 아래쪽에는 3번과 6번 블럭이 이어져있으면서 두 묶음이 연결되야한다.

2. 1번 블럭으로만 이뤄져있어야한다.

 

먼저 1번부터 확인하겠습니다. 

1번 조건의 경우 기본 모양이 위의 그림입니다.

여기에서 1번 블럭이나, 3,4,5,6 블럭이 추가되는 형태입니다.

 

5번 블럭에서 시작한다고 했을 때, 밑의 블럭이 3번 블럭이여야지 90도가 만들어집니다.

따라서 5번 블럭 밑에는 무조건 3번 블럭이 있어야합니다.

5번 블럭 아래에 3번 블럭이 없다면 될 수 있는 경우는 자신의 왼쪽 밑이 5번으로 이어지고 밑 블럭이 1번이여야 됩니다.

정리해보자면 5번 블럭일 경우

1. 자신의 밑 블럭이 3번이면 끝

2. 자신의 밑 블럭이 1번이면서 왼쪽 아래 블럭이 5번이면 해당 블럭으로 이동

 

3번 블럭도 마찬가지입니다. 자신의 오른쪽 블럭이 6번 블럭이여야지 90도가 만들어집니다.

하지만 밑의 블럭이 1이면서 오른쪽 아래가 3번 블럭이면 이어지는 블럭임으로 해당 블럭으로 이동한 뒤 다시 6번 블럭을 찾아주면 됩니다.

 

해당 경우를 5, 3, 6, 4번 블럭 모두 해주면 됩니다.

여기서 4번 블럭은 5번 블럭을 만나면 끝납니다. 따라서 4번에서 옮겨진 5번 블럭과 이어진 5번 블럭들을 모두 확인해 시작한 위치의 5번 블럭을 찾을 수 있다면 직사각형을 만들 수 있습니다.

 

하지만 큰 직사각형이 만들어 졌을 때, 내부에 1번이 아닌 다른 블럭이 있을 수도 있습니다. 해당 경우는 직사각형이 아니니 내부에 다른 블럭이 있는지 찾아줘야합니다.

 

 

2번 조건은 이루어진 모든 사각형이 1번 블럭이여야 합니다.

따라서 BFS 탐색을 통해 이어진 1번 블럭을 모두 찾습니다.

X번째 행에 있는 1번 블럭들이 서로 연결되어 있는지 && X-1번째 행과 열의 갯수가 같은지를 확인해야합니다.

X-1번째 행과 열의 갯수가 다르다면 직사각형이 안되며, 1번 블럭들이 연결되어 있지 않다면 이또한 직사각형이 아닙니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>

using namespace std;

char map[31][31];
int remake_map[11][11]; // 새로운 map을 저장
int check[11][11];      // 직사각형이 만들어 진 곳이 1 아니면 0
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int N, M;
int Rec[4][4] = { // case_1 사각형이 만들어 질 경우의 수
	{5,3,6,4},
	{3,6,4,5},
	{6,4,5,3},
	{4,5,3,6}
};
char blocks[6][3][3] = { // 간략화를 하기 위한 배열
	{{'.','.','.'}, {'.','.','.'}, {'.','.','.'}},
	{{'#','#','#'}, {'#','#','#'}, {'#','#','#'}},
	{{'#','.','.'}, {'#','#','.'}, {'#','#','#'}},
	{{'#','#','#'}, {'.','#','#'}, {'.','.','#'}},
	{{'#','#','#'}, {'#','#','.'}, {'#','.','.'}},
	{{'.','.','#'}, {'.','#','#'}, {'#','#','#'}}
};

void Remake(int x, int y) { // map을 간략화
	for (int k = 0; k < 6; k++) {
		int Same = 0;
		for (int i = 1; i <= 3; i++) {
			for (int j = 1; j <= 3; j++) {
				if (map[i + (x - 1) * 3][j + (y - 1) * 3] == blocks[k][i - 1][j - 1]) Same++;
			}
		}
		if (Same == 9) {
			remake_map[x][y] = k + 1;
			return;
		}
	}
	remake_map[x][y] = -(map[2 + (x - 1) * 3][2 + (y - 1) * 3] - '0');
}

bool number_block_surround(int x, int y) { // K개의 삼각형이 있는지?
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
			if (remake_map[xx][yy] >= 3 && remake_map[xx][yy] <= 6) cnt++;
		}
	}
	if (cnt == -remake_map[x][y]) return true;
	else return false;
}

bool rec_case_1(int x, int y, int k) { // 5,3,4,6번으로 시작하는 사각형 
	P surround[11] = { {0,0}, }; // 행을 기준으로 삼각형이 시작하는 부분과 끝나는 부분을 저장
	surround[x] = { y,y };      // 첫번째 삼각형이 나오는 곳
	int xx = x, yy = y;
	while (1) {  //다음 블럭으로 이어갈 수 있는지?
		if (xx > N || yy > M || yy < 1 || xx < 1) return false;
		if (remake_map[xx + 1][yy] == Rec[k][1]) {
			xx = xx + 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
			break;
		}
		else if (remake_map[xx + 1][yy] != 1) {
			return false;
		}
		if (remake_map[xx + 1][yy - 1] == Rec[k][0]) {
			xx = xx + 1;
			yy = yy - 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
		}
		else return false;
	}
	while (1) {
		if (xx > N || yy > M || yy < 1 || xx < 1) return false;
		if (remake_map[xx][yy + 1] == Rec[k][2]) {
			yy = yy + 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
			break;
		}
		else if (remake_map[xx][yy + 1] != 1) {
			return false;
		}
		if (remake_map[xx + 1][yy + 1] == Rec[k][1]) {
			xx = xx + 1;
			yy = yy + 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
		}
		else return false;
	}
	while (1) {
		if (xx > N || yy > M || yy < 1 || xx < 1) return false;
		if (remake_map[xx - 1][yy] == Rec[k][3]) {
			xx = xx - 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
			break;
		}
		else if (remake_map[xx - 1][yy] != 1) {
			return false;
		}
		if (remake_map[xx - 1][yy + 1] == Rec[k][2]) {
			xx = xx - 1;
			yy = yy + 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
		}
		else return false;
	}
	while (1) {
		if (xx > N || yy > M || yy < 1 || xx < 1) return false;
		if (remake_map[xx][yy - 1] == Rec[k][0]) {
			yy = yy - 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
			break;
		}
		else if (remake_map[xx][yy - 1] != 1) {
			return false;
		}
		if (remake_map[xx - 1][yy - 1] == Rec[k][3]) {
			xx = xx - 1;
			yy = yy - 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
		}
		else return false;
	}
	while (1) {
		if (xx > N || yy > M || yy < 1 || xx < 1) return false;
		if (xx == x && yy == y) break;
		if (remake_map[xx + 1][yy - 1] == Rec[k][0]) {
			yy = yy - 1;
			xx = xx + 1;
			if (surround[xx].first == 0 && surround[xx].second == 0) surround[xx] = { yy,yy };
			else surround[xx] = { min(surround[xx].first, yy), max(surround[xx].second, yy) };
		}
		else return false;
	}
	for (int i = 1; i <= N; i++) { // 내부에 삼각형이 있는지?
		for (int j = surround[i].first + 1; j <= surround[i].second - 1; j++){
			if(remake_map[i][j] != 1) return false;
		}
	}
	for (int i = 1; i <= N; i++) { // 삼각형 내부와 외부를 모두 1로 만들어 준다.
		for (int j = surround[i].first; j <= surround[i].second; j++){
			check[i][j] = 1;
		}
	}
	return true;
}

bool rec_case_2(int x, int y) { // 모두 1번 블럭으로 이루어진 경우
	vector<int> rectan[11]; // X번째 행에서 삼각형이 몇번째 열에 있는가? -> 순서대로 있지 않으면 직사각형이 아님
	queue<P> q;
	q.push({ x,y });
	check[x][y] = 1;
	rectan[x].push_back(y);
	while (!q.empty()) {
		int X = q.front().first;
		int Y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = X + dx[i];
			int yy = Y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
				if (check[xx][yy] == 0 && remake_map[xx][yy] == 1) { // 해당 조건을 만족하면 이어진 1번 블럭이다.
					check[xx][yy] = 1;
					rectan[xx].push_back(yy); // 이어진 블럭이니 해당 행에 열의 값을 넣는다.
					q.push({ xx,yy });
				}
			}
		}
	}
	for(int i = x; i <= 10; i++){
		if(rectan[i].size() == 0) break; // X번째 행에서 열에 있는 삼각형이 없다면 탐색이 끝난 것이다.
		sort(rectan[i].begin(), rectan[i].end()); // 열의 값을 정렬해 1씩 차이가 나는지 확인하기 위함
		if(rectan[i].size() != rectan[x].size()) return false; // 이전의 행과 열의 갯수가 다르다면 직사각형이 아님
		for(int j = 1; j < rectan[i].size(); j++){
			if(rectan[i][j] != rectan[i][j-1] + 1) return false; // 이어져 있지 않다면 직사각형이 아님
		}
	}
	return true;
}

void solve() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			Remake(i, j);
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (remake_map[i][j] <= 0) {
				if (!number_block_surround(i, j)) {
					cout << "NO";
					return;
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if(check[i][j] == 0){
				if (remake_map[i][j] == 5) {
					if (!rec_case_1(i, j, 0)) { //해당하는 사각형은 5번 블록으로 시작
						cout << "NO";
					return;
					}
				}
				if (remake_map[i][j] == 3) {
					if (!rec_case_1(i, j, 1)) { //해당하는 사각형은 3번 블록으로 시작
						cout << "NO";
					return;
					}
				}	
				if (remake_map[i][j] == 6) {
					if (!rec_case_1(i, j, 2)) { //해당하는 사각형은 6번 블록으로 시작
						cout << "NO";
					return;
					}
				}
				if (remake_map[i][j] == 4) {
					if (!rec_case_1(i, j, 3)) { //해당하는 사각형은 4번 블록으로 시작
						cout << "NO";
					return;
					}
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (remake_map[i][j] == 1 && check[i][j] == 0) {
				if (!rec_case_2(i, j)) { //해당하는 사각형은 1번 블록으로 시작
					cout << "NO";
					return;
				}
			}
		}
	}
	
	cout << "YES";
	
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N * 3; i++) {
		for (int j = 1; j <= M * 3; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요