[PS]#Ema's Supercomputer

 

---

 

 

https://www.hackerrank.com/challenges/two-pluses/problem

Ema's Supercomputer | HackerRank

 

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

using namespace std; 

#define PII pair<int, int> 

PII dir[4] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; 
bool visit[16][16] = { false, };

bool Check(vector<string>& grid, int y, int x, int n, int m, int range, bool bv) 
{ 
    for (int i = 0; i < 4; ++i) 
    { 
        int ny = y + (range * (dir[i].first)), nx = x + (range * (dir[i].second)); 
        if (ny < 0 || ny >= n || nx < 0 || nx >= m || grid[ny][nx] == 'B') return false; 
        if (bv && visit[ny][nx]) return false; 
    } 
    return true; 
}

void SetVisit(vector<string>& grid, int y, int x, int n, int m, int cnt) 
{ 
    for(int j = 0; j <= cnt; ++j) 
    { 
        for (int i = 0; i < 4; ++i) 
        { 
            int ny = y + (j * (dir[i].first)), nx = x + (j * (dir[i].second)); 
            visit[ny][nx] = true; 
        } 
    } 
}

int DFS(vector<string>& grid, int y, int x, int n, int m, int cnt) 
{ 
    if (Check(grid, y, x, n, m, cnt, false) == false) return 0; 
     
    int result = 0; 
    int aa = 1 + (cnt * 4); 
    memset(visit, 0, sizeof(visit)); 
    SetVisit(grid, y, x, n, m, cnt); 
    for (int j = 0; j < n; ++j) 
    { 
        for (int i = 0; i < m; ++i) 
        { 
            if (visit[j][i] || grid[j][i] == 'B') continue; 
            int bb = 1, num = 0; 
            while (1) 
            { 
                ++num; 
                if (Check(grid, j, i, n, m, num, true) == false) break; 
            } 
            bb += ((num - 1 )* 4); 
            int cc = aa * bb; 
            result = max(result, aa * bb); 
        } 
    } 
    result = max(result, DFS(grid, y, x, n, m, cnt + 1)); 
    return result; 
}

int solution(vector<string> grid) 
{ 
    int n = grid.size(), m = grid[0].size(); 
    int answer = 0; 
    vector<vector<int>> vec(n, vector<int>(m)); 
    for (int j = 0; j < n; ++j) 
    { 
        for (int i = 0; i < m; ++i) 
        { 
            vec[j][i] = DFS(grid, j, i, n, m, 0); 
        } 
    } 
    for (int j = 0; j < n; ++j) 
    { 
        for (int i = 0; i < m; ++i) 
        { 
            answer = max(answer, vec[j][i]); 
        } 
    } 
    return answer; 
}

 

 

* 문제 풀이 과정

 

결국, 경우의 수를 구하는 문제였음.

첫 번째, 두 번째 모양 모두 만들어질 수 있는 경우의 최대를 구해야함.

 

1. 만족하는 사각형 갯수는 1,5,9,13,17....으로 1의 경우부터 DFS 수행.

2. 모든 정점을 돌면서 만든 사각형의 위치를 뺀 나머지 조건을 만족하는 사각형 갯수 구하기.

3. 첫 번째 사각형 갯수 ( aa ) 와 두 번째 사각형 갯수 ( bb ) 의 최댓값 result 구하기.

4. 다시 DFS 수행하면서 5,9,13,... 확인하며 반복 수행.

 

 

무조건 최대인 개수로 구해야지만 최대 값이 나오는 것이 아님.

마지막 예제에선 최대로 큰 값이 17 이지만, 9 * 9 = 81 로 최대 값이 나옴.

 

 

 

* 해결 과정 문제점

 

DFS 중간의 while 문 세부적인 로직 문제, 과정 대입을 잘못함.

 

 

 

---