[알고리즘] 백준 21608 - 상어 초등학교 (C++)

[문제 링크] : https://www.acmicpc.net/problem/21608

#include <iostream>
#include <vector>
using namespace std;

int N, Ans;
int Arr[21][21];
int Dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int Score[5] = {0, 1, 10, 100, 1000};
vector<int> V[401];

void solve(int idx){
    int a[N][N];
    int b[N][N];
    int maxi = -1, y = 0, x = 0, tmp = 0, cnt = 0;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(Arr[i][j] != 0){
                continue;
            }

            cnt = 0;
            tmp = 0;

            for(int d=0; d<4; d++){
                int ny = i + Dir[d][0];
                int nx = j + Dir[d][1];

                if(ny < 0 || ny >= N || nx < 0 || nx >= N){
                    continue;
                }
                if(Arr[ny][nx] == 0){
                    cnt++;
                }

                for(int k=0; k<4; k++){
                    if(Arr[ny][nx] == V[idx][k]){
                        tmp++;
                    }
                }
            }

            a[i][j] = cnt;
            b[i][j] = tmp;

            if(maxi < tmp){
                maxi = tmp;
                y = i;
                x = j;
            }
            else if(maxi == tmp){
                if(a[i][j] > a[y][x]){
                    y = i;
                    x = j;
                }
                else if(a[i][j] == a[y][x]){
                    if(i < y){
                        y = i;
                        x = j;
                    }
                    else if(i == y){ 
                        if(j < x){
                            y = i;
                            x = j;
                        }
                    }
                }
            }
        }
    }
    Arr[y][x] = idx;
    return;
}

int main(){
    cin >> N;
    int idx, inp;

    for(int i=0; i<N*N; i++){
        cin >> idx;
        for(int j=0; j<4; j++){
            cin >> inp;
            V[idx].push_back(inp);
        }
        solve(idx);
    }

    int cnt = 0, cost = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cost = Arr[i][j];
            cnt = 0;
            for(int d=0; d<4; d++){
                int ny = i + Dir[d][0];
                int nx = j + Dir[d][1];

                if(ny < 0 || nx < 0 || ny >= N || nx >= N){
                    continue;
                }

                for(int k=0; k<4; k++){
                    if(Arr[ny][nx] == V[cost][k]){
                        cnt++;
                    }
                }
            }
            Ans += Score[cnt];
        }
    }
    cout << Ans << "\n";
    return 0;
}