BOJ 21608 - 상어초등학교(C++)

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

21608번: 상어 초등학교

자리를 정하는 것에 대한 조건 

1. 비어있는 칸 중에 좋아하는 학생이 인접한 칸에 많은 칸으로 정함

2. 1을 만족하는 것이 여러 개라면, 인접한 칸중에 비어있는 칸이 가장 많은 칸으로 정함

3. 2를 만족하는 칸도 여러개인 경우, 행의 번호는 가장 작은 칸으로, 그러한 칸도 여러개라면 열의 번호가 가장 작은 칸으로 정함

풀이

1. 자리 정하기와 점수계산를 위해 학생마다 좋아하는 학생의 번호들을 이차원 배열에 저장

2. 한명의 학생마다 2중 for문을 통해 비어있는 모든 자리를 확인

   2-1. 행/열 번호, 인접한 칸의 좋아하는 학생의 수, 비어있는 칸의 수를 배열에 저장

3. 2의 결과인 배열을 자리를 정하는 조건으로 정렬, 첫번째 요소의 행/열 값에 학생을 배치후 다음 학생에 대해 2를 실시

4. 모든 학생에 대해 자리를 배치후 만족도를 조사

 

 

#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[21][21];
int dy[] = {1,0,-1,0};
int dx[] = { 0,1,0,-1 };
int N;
int like[4001][4];

struct info {
    int i, j, like_cnt, blank_cnt;
};

pair<int, int> check(int now, int y, int x) { //해당 자리에 대해 인접 칸의 좋아하는 학생 수, 비어있는 수를 구함
    pair<int, int> res;
    for (int d = 0; d < 4; d++) {
        int ny = y + dy[d];
        int nx = x + dx[d];
        if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
        if (arr[ny][nx] == 0)
            res.second++;
        else {
            for (int i = 0; i < 4; i++) {
                if (like[now][i] == arr[ny][nx]) {
                    res.first++;
                    break;
                }
            }
        }
    }
    return res;
}

bool cmp(info a, info b) { //자리를 정하는 조건
    if (a.like_cnt >= b.like_cnt) {
        if (a.like_cnt == b.like_cnt) {
            if (a.blank_cnt >= b.blank_cnt) {
                if (a.blank_cnt == b.blank_cnt) {
                    if (a.i <= b.i) {
                        if (a.i == b.i) {
                            if (a.j < b.j) {
                                return true;
                            }
                            return false;
                        }
                        return true;
                    }
                    return false;
                }
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}

void select(int now) {
    vector<info> info_v;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] != 0)continue; //해당 자리가 비어있지 않으면 continue
            pair<int, int> ans = check(now, i, j);// 좋아하는 사람 수, 빈칸 수
            info_v.push_back(info{ i,j,ans.first, ans.second });
        }
    }
    sort(info_v.begin(), info_v.end(), cmp);
    arr[info_v[0].i][info_v[0].j] = now;
}

int score() {
    int answer = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int satisfaction = 0;
            for (int d = 0; d < 4; d++) {
                int ny = i + dy[d];
                int nx = j + dx[d];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                for (int l = 0; l < 4; l++) {
                    if (like[arr[i][j]][l] == arr[ny][nx]) {
                        satisfaction++;
                        break;
                    }
                }
            }
            answer += pow(10, satisfaction-1);
        }
    }
    return answer;
}

int main() {
    cin >> N;
    for (int i = 0; i < N * N; i++) {
        int num;
        cin >> num;
        cin>> like[num][0] >> like[num][1] >> like[num][2] >> like[num][3];
        select(num);
    }
    cout << score();
    return 0;
}