[시즌2] 17085번 십자가 2개 놓기

문제 : 중요한 부분 형광펜 칠하기.

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

17085번: 십자가 2개 놓기

문제

십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다.

아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈칸은 '.'이다.

                  ...*...
          ..*..   ...*...
    .*.   ..*..   ...*...
*   ***   *****   *******
    .*.   ..*..   ...*...
          ..*..   ...*...
                  ...*...

십자가의 넓이는 포함된 '*'의 개수이다. 크기가 0, 1, 2, 3인 십자가의 넓이는 1, 5, 9, 13이다.

크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다. 격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다. 십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자.

입력

첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다.

1. 문제 분석

"십자가의 크기는 0보다 크거나 같아야 한다."

- 반대로 생각을 해보면, 십자가의 크기가 1부터 시작한다고 생각할 수 있습니다.

"크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다."

- 격자판은 char 형식으로 작성할 수 있겠다.

"격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다."

- 이 말은, 십자가가 덮으면 안 된다. 겹쳐져서는 안 된다는 의미, 즉 자신의 범위가 존재한다.

"십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자."

- 십자가가 놓일 수 있는 조건이 됩니다.

"격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다."

- 입력값의 가로, 세로의 너비는 무척이나 작다.

2. 왜 이렇게 접근했는가?

입력값이 상당히 작고, 십자가가 놓일 수 있는 곳이 정해져 있다.('#'이 있는 부분만 위치할 수 있다.)

- 입력값이 작다. : 완전 탐색 (Brute Force)가 가능하다.

- 십자가가 놓일 곳이 정해져 있다. : 각 그리드의 모든 조합을 확인해 보자. 

3. 예외 케이스 또는 주의할 점은 무엇이 있을까?

예외 케이스...는 문제를 구현한 후 생각해봐야 할 것 같다. 단순히 각 점에서 십자가의 크기를 키워나가는 것이기 때문에 어떠한 문제가 발생할지 지금 당장 감이 잡히지 않는다. 또한, 주의해야 할 점은  각 십자가를 놓을 때 크기를 어떻게 지정해줘야 하지? 그 부분을 생각해야 될 것 같다. 

예외 케이스는 큰 의미는 없는것 같다. 원하는 바를 정확하게 구현하면 되는 문제입니다.

(1) 십자가가 놓일 위치 조합을 통해서 전체 구하기

(2) 십자가가 커가는 것을 구현하기

- 하나씩 십자가를 키워나가는 것

- 한 번에 십자가를 키우는 것이 아님. 완전탐색이 필요함.

4. 빠른 구현을 위한 기술 또는 구현 방식

1. '#'이 들어간 곳에 십자가를 놓을 것이기 때문에 모든 십자가가 가능한 위치를 구한다.

2. 총 두개의 십자가를 생성할 것이기 때문에, 전체 조합에서 두개를 거를 수 있는 조합을 선택한다.

3. 골라진 두개의 십자가 위치에서 십자가가 커질 수 있을 때까지 구한다.

- 십자가가 제일 커질 수 있는 크기는 7이 한계이다. 이유는 N,M의 크기가 15 이하이기 때문이다.

4. 십자가의 위치에 둘다 1개의 십자가를 설치하고, 가능한지 체크를 하자.

- 십자가의 최대 크기를 구하는 문제이다.

- 하나의 십자가가 크게되면, 최댓값을 구하지 못한다. 두 개가 평등하게 커야 한다. 어느 십자가가 먼저 커지는 가는 상관이 없다. 이유는 어느 십자가가 먼저 커지든 곱하는 것이기 때문이다.

5. 하나하나 계산을 해서 총 십자가의 개수를 구할 수 있다.

5. 구현 완료

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

#define MAX 16
using namespace std;

int n,m,vis[MAX][MAX];
char board[MAX][MAX];

vector<int> visited;
vector<pair<int,int> > sharp;

void init(){
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
			if(board[i][j] == '#') sharp.push_back({i,j});
		}
	}
	
}

int ans = 1;

const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};

bool isRange(int y, int x){
	return 0 <= y && y < n && 0 <= x && x < m;
}

bool chk(int num, int range){
	
	int y = sharp[num].first;
	int x = sharp[num].second;
	
	int cnt = 0;
	vector<pair<int,int> > v;
	
	for(int i = 0; i < 4; i++){
		
		int ny = y + (dy[i] * range);
		int nx = x + (dx[i] * range);
		
		if(!isRange(ny,nx)) return false;
		if(vis[ny][nx]) return false;
		if(board[ny][nx] == '.') return false;
		
		cnt++;
		v.push_back({ny,nx});
	}
	
	if(cnt == 4){
		for(int i = 0; i < 4; i++) vis[v[i].first][v[i].second] = 1;
		return true;
	}
	
}

void printAll(){
	
	cout << "select!" << "\n";
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << vis[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	
//	cout << "crossA : " << crossA << " " << "crossB : " << crossB << "\n";
	
}

int calc(int a, int b){
	
	int res = 1;
	
	int crossA = 1, crossB = 1;
	bool chkA = true; bool chkB = true;
	
	vis[sharp[a].first][sharp[a].second] = 1;
	vis[sharp[b].first][sharp[b].second] = 1;
	
	for(int i = 1; i <= 7; i++){
		
		if(chk(a,i) && chkA) crossA = (4 * i + 1);
		else chkA = false;
		
		if(chk(b,i) && chkB) crossB = (4 * i + 1);
		else chkB = false;
	}
	
	//printAll();
	
	return crossA * crossB;
		
}

int main(){
	
	init();
	
	for(int i = 0; i < sharp.size() - 2; i++) visited.push_back(0);
	for(int i = 0; i < 2; i++) visited.push_back(1);
	
	sort(sharp.begin(),sharp.end());
	sort(visited.begin(), visited.end());
	
	int cnt = 0;
	
	do{
		
		memset(vis,false,sizeof(vis));
		
		vector<int> loc;
		for(int i = 0; i < visited.size(); i++) if(visited[i]) loc.push_back(i);
		
		ans = max(ans,calc(loc[0], loc[1]));
				
	}while(next_permutation(visited.begin(), visited.end()));
	
	cout << ans;

	return 0;
}

* 문제 풀이는 항상 C++ 로 진행하고 있습니다.

* 해당 글에 대한 댓글 달아주시면 깊이 생각해 답글 달아드리겠습니다.