(C++) - 백준(BOJ) 21608번 : 상어 초등학교

www.acmicpc.net/problem/21608

21608번: 상어 초등학교

구현 문제였습니다.

 

풀이방법

 1. x번 학생이 좋아하는 사람이 i,j자리에 앉아있으면 그 자리의 인접칸들중 비어있는 칸들마다 1씩 더해줍니다. 이런식으로 가중치를 부여하면 그 최대값과 같은 자리들을 possibleSeats vector변수에 넣어줍니다.

 

 2. possibleSeats를 first, second 순으로 기준을 두어 오름차순으로 정렬합니다. 이들 좌표의 인접 칸에 대해 빈 칸들을 세주고 이들 정보를 emptyCnt vector변수에 push_back해줍니다. 그 후 최대 빈칸 수 에 해당하는 i,j에 x학생을 앉힙니다.

 

 3. 모두 앉힌 후 점수를 계산합니다. i,j에 앉아있는 학생 student의 좋아하는 학생들이 인접칸에 몇 명이 있는지 세준 후  변수 cnt에 저장합니다. 그 후 점수 += 10^(cnt-1) 해줍니다. 모든 i,j에 대해 수행한 뒤 최종 점수를 반환해 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, board[21][21], likeBoard[21][21];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
vector <int> info[500];
vector <pii> possibleSeats;

void findMaxEmptyBlock(int studentNum){
    sort(possibleSeats.begin(),possibleSeats.end());
    vector <int> emptyCnt;
    int maxCnt = 0;
    for(auto c : possibleSeats){
        int cnt = 0;
        for(int i = 0; i < 4; i++){
            int nx = c.first + dx[i];
            int ny = c.second + dy[i];
            if(1 > nx || nx > n || 1 > ny || ny > n) continue;
            if(board[nx][ny]) continue;
            cnt++;
        }
        maxCnt = max(maxCnt,cnt);
        emptyCnt.push_back(cnt);
    }

    for(int i = 0; i < emptyCnt.size(); i++){
        if(emptyCnt[i] == maxCnt){
            board[possibleSeats[i].first][possibleSeats[i].second] = studentNum;
            return;
        }
    }
}

void findLikeSquare(int studentNum){
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int num = 0; num < info[studentNum].size(); num++){
                if(board[i][j] != info[studentNum][num]) continue;
                for(int dir = 0; dir < 4; dir++){
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if(1 > nx || nx > n || 1 > ny || ny > n) continue;
                    if(board[nx][ny]) continue;
                    likeBoard[nx][ny]++;
                }
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cnt = max(cnt,likeBoard[i][j]);
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(cnt == likeBoard[i][j] && !board[i][j]){
                possibleSeats.push_back({i,j});
            }
        }
    }
}

int getSatisfied(){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int student = board[i][j];
            int cnt = 0;
            for(int k = 0; k < 4; k++){
                int nx = i + dx[k];
                int ny = j + dy[k];
                if(1 > nx || nx > n || 1 > ny || ny > n) continue;
                for(int num = 0; num < info[student].size(); num++){
                    if(info[student][num] != board[nx][ny]) continue;
                    cnt++;
                }
            }
            sum += pow(10,cnt-1);
        }
    }
    return sum;
}

int main(){
    cin >> n;
    for(int i = 0; i < n*n; i++){
        possibleSeats.clear();
        memset(likeBoard,0,sizeof(likeBoard));
        int x, like;
        cin >> x;
        for(int i = 0; i < 4; i++) {
            cin >> like;
            info[x].push_back(like);
        }
        findLikeSquare(x);
        findMaxEmptyBlock(x);
    }
    cout << getSatisfied();
}