[Algorithm] Baekjoon 1025번 : 제곱수 찾기

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

1025번: 제곱수 찾기

int n, m;
vector<string> arr;
unordered_map<int, bool> sqrNums;
 
int dirs[8][2] = {
                {-1,0}, {1,0}, {0,-1}, {0,1},
                {-1,-1}, {-1,1}, {1,1}, {1,-1}  
                };
 
bool checkInRange(int y, int x)
{
    if (y < 0 || y >= n || x < 0 || x >= m) return false;
    return true;
}
 
bool checkSqrNum(int num)
{
    int temp = sqrt(num);
    return temp * temp == num;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
        arr.push_back(s);
    }
 
    int maxNum = -1;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            string s = "";
            s += arr[i][j];
            int sNum = stoi(s);
 
            if (checkSqrNum(sNum)) maxNum = max(maxNum, sNum);
 
            for (int d = 0; d < 8; ++d)
            {
                for (int offY = 1; offY <= 8; ++offY) // offset값 
                {
                    for (int offX = 1; offX <= 8; ++offX)
                    {
                        int curY = i + dirs[d][0] * offY;
                        int curX = j + dirs[d][1] * offX;
                        string ts = s;
 
                        while (1)
                        {
                            if (!checkInRange(curY, curX)) break;
                            ts += arr[curY][curX];
                            int num = stoi(ts);
 
                            if (checkSqrNum(num)) maxNum = max(maxNum, num);
 
                            curY += dirs[d][0] * offY;
                            curX += dirs[d][1] * offX;
                        }
                    }
                }
            }
        }
    }
 
    cout << maxNum;
}

깔끔한 완전탐색문제이다.

모든 원소에 대해 8방향(상하좌우,각 대각선 총 4개)에 대해서 뻗어나가면서 숫자를 만들고 완전제곱수인지 검사할 건데, +1씩 뻗어나가는게 아니라 행과 열에 대해 '등차'를 유지만 하면 숫자를 만들 수 있다.

즉 행값은 +1, 열값은 +2씩 증가...하는 형태도 될 수 있다. (해당 백준링크의 맨 마지막 테스트케이스를 꼭 보기를 바란다)