개발 블로그

문제 링크 : https://www.acmicpc.net/problem/17085

문제

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

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

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

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

입력

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

출력

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

접근 방법

첫번째 십자가의 가능한 크기가 0부터 max라고 했을 때,

모든 경우에 대해, 두번째 십자가의 가능한 크기를 모두 구해서 최대 넓이를 구하는 방식이다. 

처음에는,

십자가 중심 2개를 (r1, c1), (r2, c2) 라고 했을 때, DFS를 이용하여 모든 (r1, c1), (r2, c2) 의 조합을 구했다. 

그 후, 십자가 두개의 크기를 각각 1씩 증가시켜 나가면서 넓이를 구했다.

그러나 이 방식은 완전탐색이 아니다.

왜냐하면 1번 십자가의 크기를 1 증가시킨 후 -> 1번과 2번 십자가가 겹치지 않는 한에서 2번 십자가의 크기를 1 증가한 뒤 넓이를 계산했기 때문이다. 완전탐색을 하려면 반대 순으로도 넓이를 각 경우에 대해 계산해야하며, 중간에도 계산을 한번 더 해야한다. 

즉,  아래와 같이 여러번의 계산이 필요한 것이다. 

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

또한, 아래 링크의 테스트케이스는 4달 전에 추가된 데이터로, 이 경우도 주의해야한다. 

이렇게 두가지 고려할 점이 있지만 

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

이 방식으로 그냥 모든 가능한 경우를 완전탐색하면 보다 단순하게 해결 가능하다.

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;

int N, M;
char map[15][15];
int answer = 0;

//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

//(r,c)가 중심일 때, 가능한 십자가의 최대 크기
int getSize(int r, int c){  
    int ret = 0;
    while(1){
        bool flag = true;
        for(int i = 0; i<4; i++){
            int nr = r + dr[i]*ret;
            int nc = c + dc[i]*ret;
            if(nr<0 || nc<0 || nr>=N || nc>=M || map[nr][nc] != '#'){
                flag = false;
                break;
            }
        }
        if(flag) ret++;
        else break;
    }
    return ret - 1; //ret가 0부터 시작하므로, 처음 통과하면 ret=1이 되는데 이때 십자가의 크기는 0임 ('*' 한개짜리)
}

//중심이 (r,c)이고 크기가 K인 십자가를 만들거나(val='#') 십자가 원상복구(val='.')
void make_cross(int r, int c, int k, int val){ 
    for(int i = 0; i<=k; i++){
        for(int j = 0; j<4; j++){
            int nr = r + dr[j]*i;
            int nc = c + dc[j]*i;
            map[nr][nc] = val;
        }
    }
}

int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }


    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(map[i][j] == '#'){
                int step1 = getSize(i,j);
                for (int k = 0; k <= step1; k++)    //첫번째 십자가 크기 1부터 max까지, 
                {
                    make_cross(i,j,k,'*');  //첫번째 십자가 표시

                    for(int r = 0; r<N; r++){
                        for(int c=0; c<M; c++){
                            if(map[r][c] == '#'){
                                int step2 = getSize(r,c); //각 크기에 대해 두번째 십자가 크기 구하기
                                int width1 = 4*k + 1;
                                int width2 = 4*step2 + 1;
                                answer = max(answer, width1*width2);
                            }
                        }
                    }
                    make_cross(i,j, k, '#');    //첫번째 십자가 원상복구


                }
            } 
        
            
        }
    }
    
   
    cout << answer;

    return 0;
}

(참고 : https://www.acmicpc.net/source/30665990)