[ 백준 21608 ] 상어 초등학교 (C++) - 구현, BruteForce

---

🔗 문제 링크

21608번: 상어 초등학교

---

💡 문제 풀이 및 해석

1. N이 최대 20이고, 교실의 크기는 20*20 이므로 400이다.
2. 모든 칸에서 인접한 칸을 조사해도 400*4 밖에되지 않는다.
3. 학생들의 배치는 BruteForce로 하고 만족도 또한 BruteForce로 해도 10만번으로 끝낼 수 있다.
   코드에 대한 자세한 설명은 주석에 달아뒀다.

---

⭐️ 정답 코드 및 설명

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

using namespace std;

int N;
int MAP[21][21];
int near_x[] = { -1,1,0,0 };
int near_y[] = { 0,0,1,-1 };
queue<int> q;
vector<int> ML[401]; // MyLike

void input() {
    cin >> N;
    for (int i = 0; i < N * N; i++) {
        int student;
        cin >> student;
        q.push(student);
        for (int j = 0; j < 4; j++) {
            int Like;
            cin >> Like;
            ML[student].push_back(Like);
        }
    }
}

void sol() {
    long long answer = 0;
    while (!q.empty()) {
        int student = q.front(); q.pop();
        priority_queue<pair<int, pair<int, pair<int, int>>>> pq;
        for (int y = 1; y <= N; y++) {
            for (int x = 1; x <= N; x++) {
                if (MAP[y][x] != 0) continue; // 이미 배정된 자석은 패스
                int NearF = 0, NearS = 0; // 인접한 친한친구 & 인접한 빈좌석
                for (int i = 0; i < 4; i++) {
                    int nx = x + near_x[i], ny = y + near_y[i];
                    if (nx > 0 && nx <= N && ny > 0 && ny <= N) { // 인접한 범위 안
                        if (MAP[ny][nx] == 0) NearS++;
                        // 친한 친구가 인접한 칸에 있다면
                        else if (find(ML[student].begin(), ML[student].end(), MAP[ny][nx]) != ML[student].end()) {
                            NearF++;
                        }
                    }
                }
                // 친한 친구, 빈 공간, 행, 열 순으로 정렬
                pq.push({ NearF,{NearS,{-y,-x}} });
            }
        }
        int Y = -pq.top().second.second.first;
        int X = -pq.top().second.second.second;
        MAP[Y][X] = student;
    }

    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            int student = MAP[y][x];
            int NearF = 0;
            for (int i = 0; i < 4; i++) {
                int nx = x + near_x[i], ny = y + near_y[i];
                if (nx > 0 && nx <= N && ny > 0 && ny <= N) {
                    // 친한 친구가 인접한 칸에 있다면
                    if (find(ML[student].begin(), ML[student].end(), MAP[ny][nx]) != ML[student].end()) {
                        NearF++;
                    }
                }
            }
            answer += pow(10, NearF - 1);
        }
    }

    cout << answer;
}

int main() {

    input();
    sol();
    return 0;
}

---

🤔 문제 후기

처음에는 while문 한번에 해결할려고 했는데, 배치를 하면서 인접한 사람만큼 answer에 값을 더해줬다. 이는 배치된 후에 주변에 다른 학생이 배치됬을 때, 업데이트되지 않는 오류가 발생했다. 이를 해결하기 위해 배치가 완료된 후에 다시 만족도를 조사하는 방식으로 문제를 풀었다.
문제를 처음 제출하고 OutOfBounds 오류가 발생했는데, vector<int> ML[401]; // MyLike 부분을 21로 해두는 바람에 발생하였다. 자리가 최대 400석인 만큼 학생도 당연히 400명이 되어야 하는 부분인데 이 부분을 착각하여 생긴 문제였다. 문제의 조건을 그대로 구현하면 되는 문제여서 어렵진 않았지만, Gold 5 문제로는 조금 어려운 문제였던 것 같다.