백준 17085 (C++) 십자가 2개 놓기

최초 업로드: 2025-07-20 19:56:25

최근 수정 시간: 2025-07-25 07:54:58

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 십자가 2개 놓기

[문제 링크](https://www.acmicpc.net/problem/17085)

## 문제 설명

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

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

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

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

## 입력

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

## 출력

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

## 풀이
#### 백트래킹으로 깊이가 2일때까지 살펴보아주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

string s[15];

int n, m;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int dfs(int depth=0, int cnt=1) {
    if(depth==2) return cnt;

int maxCnt=1;
 for(int x=0;x<n;x++) {
 for(int y=0;y<m;y++) {
 if(s[x][y]=='#') {
 int len=0;
 s[x][y]='.';

// 크기가 1인 경우
                maxCnt = max(maxCnt, dfs(depth+1, cnt));

// 크기가 2 이상인 경우
 while(true) {
 bool chk=true;
 for(int i=0;i<4;i++) {
 int nx = x+dx[i]*(len+1);
 int ny = y+dy[i]*(len+1);
 if(nx<0 || nx>=n || ny<0 || ny>=m || s[nx][ny]=='.') {
 chk=false;
 break;
 }
 }
 if(chk) {
 len++;
 for(int i=0;i<4;i++) {
 int nx = x+dx[i]*len;
 int ny = y+dy[i]*len;
 s[nx][ny]='.';
 }
 maxCnt = max(maxCnt, dfs(depth+1, cnt*(len*4+1)));
 } else {
 break;
 }
 }

// 땅 되돌리기
 s[x][y]='#';
 for(int i=1;i<=len;i++) {
 for(int j=0;j<4;j++) {
 int nx = x+dx[j]*i;
 int ny = y+dy[j]*i;
 s[nx][ny]='#';
 }
 }
 }
 }
 }
 return maxCnt;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n >> m;
 for(int i=0;i<n;i++) cin >> s[i];
 cout << dfs();
}
```