[PS 백준 - 2.12] 17085번: 십자가 2개 놓기

문제 정보

백준 17085번 - 바로가기

• 난이도: 실버 1
• 알고리즘: 브루트포스 알고리즘

---

코멘트

이번 알고리즘 문제들 중 제일 킬러 문제였다. 그래도 아무 도움 없이 50분만에 풀어내서 정말 뿌듯했다. 내가 생각한 아이디어는 아래와 같다.

1. bool 이차원 배열 선언하여 #이면 true, . 이면 false 대입
2. 가능한 모든 크기의 십자가들의 위치를 찾고, vec에 (시작 좌표 x,y, 십자가 크기) 저장 - checkArr 함수
3. 이차원 배열 복사한 temp에서 검사, 십자가 2개씩 가져와서 십자가 위치에 “.”이 하나도 없을 경우 lists에 넓이 대입 - makeFalse 함수로 검사
4. lists를 sort하여 제일 큰 값 출력

---

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

bool checkArr(bool** arr, int a, int b, int n) {
    bool flag = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == (0.5) * (n - 1) || j == (0.5) * (n - 1)) {
                // .이면 설치 불가능! 따라서 false화
                if (!arr[a + i][b + j]) flag = false; 
            }
        }
    }
    return flag;
}

bool makeFalse(bool** arr, int a, int b, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == (0.5) * (n - 1) || j == (0.5) * (n - 1)) {
                // #이면 .으로 바꾸고, 이미 .이면 false return
                if (!arr[a + i][b + j]) return false;
                else arr[a + i][b + j] = false;
            }
        }
    }
    return true;
}

using namespace std;

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);
    
    int n, m;
    cin >> n >> m;

    bool** pan = new bool* [n];
    for (int i = 0; i < n; i++) {
        pan[i] = new bool[m];
    }

    char c;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c;
            pan[i][j] = (c == '#') ? true : false;
        }
    }
    int max = n > m ? n : m;

    // 십자가 설치 가능한지 확인하고 벡터에 좌표 등록
    vector<pair<pair<int, int>, int>> vec; // (시작 좌표 위치, 넓이)

    for (int l = 1; l <= max; l += 2) {
        for (int i = 0; i <= n - l; i++) {
            for (int j = 0; j <= m - l; j++) {

                if (checkArr(pan, i, j, l)) {
                    
                    pair<int, int> spot(i, j);
                    vec.push_back(pair<pair<int, int>, int>(spot, l));

                }
            }
        }
    }

    vector<int> lists;

    for (int a = 0; a < vec.size(); a++) {
        for (int b = a + 1; b < vec.size(); b++) {
            bool** temp = new bool* [n];
            for (int i = 0; i < n; i++) {
                temp[i] = new bool[m];
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    temp[i][j] = pan[i][j]; // 깊은 복사
                }
            }
            
            // 겹치는지 확인하고, 안 겹치면 lists에 넓이 등록
            if (makeFalse(temp, vec[a].first.first, vec[a].first.second, vec[a].second)) {
                if (makeFalse(temp, vec[b].first.first, vec[b].first.second, vec[b].second)) {
                    lists.push_back((2 * vec[a].second - 1) * (2 * vec[b].second - 1));
                }
            }
           

            for (int i = 0; i < n; i++) {
                delete[] temp[i];
            }
            delete[] temp;
        }
    }

    sort(lists.begin(), lists.end());


    cout << lists.back();

    for (int i = 0; i < n; i++) {
        delete[] pan[i];
    }
    delete[] pan;

}