백준 21608 c++ "상어 초등학교" -PlusUltraCode-

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

 

[필자 사고]

구현 문제다

문제에서 주어진 조건은 3가지다

다행이 까탈스러운 조건이 아니라 한번에 우선순위 큐를 이용하여 정렬 가능한 요구조건이다.

 

아래는 자세한 코드해설이다.

[코드 해설]

1. Input 함수

• 입력으로부터 격자의 크기 N을 받고, N×N 크기의 2차원 벡터 arr를 0으로 초기화합니다.
• 이후 N×N 명의 학생(또는 사용자) 정보가 들어오는데, 각 학생마다 자신의 번호 me와 좋아하는 친구 4명 번호(a, b, c, d)를 입력받습니다.
• 이 정보를 likes 벡터에 저장하며, 학생 번호를 키로 하여 인덱스를 빠르게 찾을 수 있도록 myMap이라는 맵에 저장합니다.

---

2. isInside 함수

• 좌표 (sero, garo)가 격자 내에 존재하는지 판단하는 함수입니다.
• 좌표가 0 이상 N 미만 범위 내에 있으면 true, 아니면 false를 반환합니다.

---

3. getCountLikeFriend 함수

• 특정 위치 (nextSero, nextGaro)에 앉아 있는 학생 번호가, 인자로 받은 friendNode가 좋아하는 친구 목록에 포함되는지를 확인합니다.
• 그 칸이 빈 칸이면 0을 반환하고, 친구 목록에 있으면 1, 아니면 0을 반환합니다.

---

4. checkLikeFriend 함수

• 현재 좋아하는 친구 정보를 가진 학생이 앉을 수 있는 최적의 자리를 찾기 위해 전체 격자를 탐색합니다.
• 이미 사람이 앉아있는 칸은 건너뛰고, 빈 칸에 대해 인접한 4방향을 검사합니다.
• 인접 칸 중 빈 칸 개수와 친구가 앉아있는 칸 개수를 각각 센 후, 우선순위 큐에 위치 정보와 함께 저장합니다.
• 우선순위 큐는 나중에 조건에 맞는 최적의 자리를 쉽게 꺼낼 수 있게 해줍니다.

---

5. checkCountFriend 함수

• 완성된 자리 배치 후, 특정 학생이 앉은 칸 (sero, garo)의 인접한 4칸을 살펴 좋아하는 친구가 몇 명 앉아있는지 세고, 그 수에 따라 점수를 반환합니다.
• 0명이면 0점, 1명 1점, 2명 10점, 3명 100점, 4명 1000점으로 가중치를 다르게 둡니다.
• 이 점수 합이 최종 만족도 점수로 활용됩니다.

---

6. Game_Start 함수

• likes 벡터 순서대로 학생들을 자리 배치합니다.
• 각 학생마다 우선순위 큐를 초기화하고, checkLikeFriend 함수로 그 학생에게 최적의 자리를 찾습니다.
• 우선순위 큐의 top 위치가 해당 학생이 앉을 자리입니다.
• 모든 학생 배치가 끝난 후, 전체 자리에서 학생별로 인접 친구 수에 따른 점수를 계산하여 합산합니다.
• 최종 점수를 출력합니다.

---

7. main 함수

• 입출력 속도 최적화 설정 후, Input 함수와 Game_Start 함수를 순서대로 호출하여 프로그램을 실행합니다.

[소스 코드]

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

struct friendNode {
    int me;
    vector<int> friends;
};

struct Node {
    int sero;
    int garo;
    int count;       // 인접 친구 수
    int emptyCount;  // 인접 빈 칸 수
};

int dy[4] = { 0, -1, 0, 1 };
int dx[4] = { 1, 0, -1, 0 };

struct cmp {
    bool operator()(const Node& a, const Node& b) {
        if (a.count != b.count)
            return a.count < b.count;          // count 큰게 우선
        if (a.emptyCount != b.emptyCount)
            return a.emptyCount < b.emptyCount; // emptyCount 큰게 우선
        if (a.sero != b.sero)
            return a.sero > b.sero;            // sero 작은게 우선
        return a.garo > b.garo;                // garo 작은게 우선
    }
};

int N;
vector<vector<int>> arr;
vector<friendNode> likes;
priority_queue<Node, vector<Node>, cmp> pq;
map<int, int> myMap;

void Input() {
    cin >> N;
    arr.assign(N, vector<int>(N, 0));

    for (int i = 0; i < N * N; i++) {
        int me;
        cin >> me;
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        likes.push_back({ me, {a, b, c, d} });
        myMap[me] = i;
    }
}

bool isInside(int sero, int garo) {
    return sero >= 0 && sero < N && garo >= 0 && garo < N;
}

// 해당 칸에 있는 번호가 node 친구 목록에 있는지 확인
int getCountLikeFriend(const friendNode& node, int nextSero, int nextGaro) {
    int friendNumber = arr[nextSero][nextGaro];
    if (friendNumber == 0) return 0;
    for (int f : node.friends) {
        if (f == friendNumber) return 1;
    }
    return 0;
}

void checkLikeFriend(const friendNode& node) {
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            if (arr[i][k] != 0) continue; // 이미 자리 있음

            int emptyCount = 0;
            int friendCount = 0;

            for (int j = 0; j < 4; j++) {
                int nextSero = i + dy[j];
                int nextGaro = k + dx[j];
                if (!isInside(nextSero, nextGaro)) continue;

                if (arr[nextSero][nextGaro] == 0) {
                    emptyCount++;
                }
                else {
                    friendCount += getCountLikeFriend(node, nextSero, nextGaro);
                }
            }
            pq.push({ i, k, friendCount, emptyCount });
        }
    }
}

int checkCountFriend(const friendNode& fNode, int sero, int garo) {
    int count = 0;
    for (int i = 0; i < 4; i++) {
        int nextSero = sero + dy[i];
        int nextGaro = garo + dx[i];
        if (!isInside(nextSero, nextGaro)) continue;

        for (int num : fNode.friends) {
            if (num == arr[nextSero][nextGaro]) {
                count++;
                break;
            }
        }
    }

    if (count == 0) return 0;
    if (count == 1) return 1;
    if (count == 2) return 10;
    if (count == 3) return 100;
    if (count == 4) return 1000;
    return 0;
}

void Game_Start() {
    for (int i = 0; i < likes.size(); i++) {
        // pq 초기화
        pq = priority_queue<Node, vector<Node>, cmp>();

        const friendNode& node = likes[i];
        checkLikeFriend(node);
        Node pqNode = pq.top();
        arr[pqNode.sero][pqNode.garo] = node.me;
    }

    int resultSum = 0;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            int nowNumber = arr[i][k];
            int index = myMap[nowNumber];
            const friendNode& fNode = likes[index];
            resultSum += checkCountFriend(fNode, i, k);
        }
    }

    cout << resultSum << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Input();
    Game_Start();

    return 0;
}