[Silver IV] 네모난 순열 찾기 1 - 34231

[문제 위치]

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

[문제 풀이]

이 문제는 브루트포스를 통해 해결하는 문제이다.
네모난 부분 배열(직사각형)을 고를 때, 그 안에 들어 있는 원소들이 1부터 K까지 정확히 한 번씩 등장하면 그것을 순열이라고 한다.
따라서 가능한 모든 직사각형을 탐색하면서, 그 안에 들어 있는 원소들을 검사해 순열 조건을 만족하는 경우를 세면 된다.
검사 방법은 원소 개수를 K라 할 때, 모든 값이 1 이상 K 이하인지 확인하고, 중복 없이 정확히 K개가 있는지 확인하는 것이다.
이 과정을 통해 전체 경우의 수를 카운트하면 답을 구할 수 있다.

아래는 이를 구현한 코드이다.

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

#define FAST ios::sync_with_stdio(false); cin.tie(0);

int main(){
    FAST;
    int N;
    cin >> N;
    vector<vector<int>> a(N, vector<int>(N));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> a[i][j];
        }
    }
    long long ans = 0;
    for(int top=0;top<N;top++){
        for(int bottom=top;bottom<N;bottom++){
            for(int left=0;left<N;left++){
                for(int right=left;right<N;right++){
                    int K = (bottom-top+1)*(right-left+1);
                    vector<bool> seen(K+1,false);
                    bool ok = true;
                    int cnt=0;
                    for(int i=top;i<=bottom && ok;i++){
                        for(int j=left;j<=right;j++){
                            int x = a[i][j];
                            if(x<1 || x>K || seen[x]){
                                ok=false;
                                break;
                            }
                            seen[x]=true;
                            cnt++;
                        }
                    }
                    if(ok && cnt==K) ans++;
                }
            }
        }
    }
    cout << ans << "\n";
}