[백준] 17085 십자가 2개 놓기

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

17085번: 십자가 2개 놓기

1. dfs 로 가능한 위치 2개를 뽑는다.

2. 맵을 카피한다.

3. 첫번째 위치에서 구할 수 있는 최대 길이를 구한다.

4. 첫번째 위치에서 넓이를 하나씩 넓혀가면서 두번째 위치에서 만들 수 있는 최대의 십자가의 넓이를 구한다.

5. 4. 의 과정을 거치면서 첫번째 넓이 * 두번째 넓이를 answer 값과 비교하여 answer 보다 크면 update 해준다.

 

처음에 실패한 이유는

십자가 두개의 크기를 각각 1씩 증가시켜가면서 넓이를 구했는데, 그럴 경우 완전탐색이 아니다.

완전 탐색으로 하려면, 

1번 십자가 크기증가, 2번 십자가 크기 1 증가 -> 넓이 계산

2번 십자가 크기증가, 1번 십자가 크기 1 증가 -> 넓이 계산

이렇게 두번을 해주어야한다. 그런데 그러니까 시간초과가 나더라...

 

그래서 다른 사람 포스팅을 찾아본 결과

첫번째 십자가의 가능한 크기가 0부터 max라고 했을 때,
모든 경우에 대해, 두번째 십자가의 가능한 크기를 모두 구해서 최대 넓이를 구하는 방식이다.

의 방식을 발견했고, 아래와 같이 구현했다.

 

여기서 볼 수 있는 것은 길이에 따라 넓이가 달라지는데 

그 식은

넓이 = 길이 * 4 + 1 

로 구현할 수 있다.

 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

int n, m;
char map[20][20];
bool visit[400];
pair<int, int> sharp[400];
int sharp_cnt;
int answer;
int choice[5];
char cmap[20][20];

void copy_map() {

	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cmap[i][j] = map[i][j];
}

// 길이를 리턴
int get_max(int y, int x) {

	int length = 1;

	while(true) {

		if(y-length < 0 || y+length >=n || x-length < 0 || x+ length >= m)
			break;

		if(cmap[y-length][x] == '#' && cmap[y+length][x] == '#' &&
		 cmap[y][x-length] == '#' && cmap[y][x+length] == '#' ) {
			length++;
		}

		else
			break;
	}
	length--;

	return length;
}

void draw(int y, int x, int length) {

	for(int i=0; i<=length; i++) {
		cmap[y-i][x] = '.';
		cmap[y+i][x] = '.';
		cmap[y][x-i] = '.';
		cmap[y][x+i] = '.';
	}

}

void solve() {

	// copy map 
	copy_map();

	int fy = sharp[choice[0]].first;
	int fx = sharp[choice[0]].second;
	int sy = sharp[choice[1]].first;
	int sx = sharp[choice[1]].second;


	int first_max = get_max(fy, fx); // 최대 길이를 구함

	for(int i=0; i<=first_max; i++) {
		// draw in copy
		draw(fy, fx, i); // 한칸씩 넓혀보기
		int first_size = 1+(4*i);

		int second_max = get_max(sy, sx); // 두번쨰의 가능한 최대 길이
		int second_size = 1 + (4*second_max); // 넓이

		answer = max(first_size * second_size, answer);
	}

}


void dfs(int idx, int cnt) {
	if(cnt == 2) {
		solve();
		return;
	}

	for(int i=idx; i<sharp_cnt; i++) {
		if(visit[i]) continue;
		visit[i] = true;
		choice[cnt] = i;
		dfs(i, cnt+1);
		visit[i] = false;
	}

}
int main() {

	scanf("%d %d\n", &n, &m);

	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++) {
			cin >> map[i][j];
			if(map[i][j] == '#') {
				sharp[sharp_cnt++] = make_pair(i, j);
			}
		}

	dfs(0, 0);

	printf("%d\n", answer);

}

dfs 가 어려운 문제는 아니었지만 조합을 구한 후에 과정이 좀 구현이 빡센 문제들이 슬슬 나오기 시작한다...

화이팅...ㅠㅠ