[BOJ] 21608 : 상어 초등학교

문제 링크

21608번: 상어 초등학교 (acmicpc.net)

21608번: 상어 초등학교

조건에 맞게 학생들을 자리에 배치하는 단순 구현 문제.

풀이

자리에 배치하기 위해 필요한 정보

1. 각 학생들이 좋아하는 학생의 번호

2. 학생들을 배치 할 순서

1번은 Like라는 int형 벡터를 배열로 선언해서 정보를 저장했다. Like[ i ]에는 i학생이 좋아하는 학생들의 번호가 들어가있다.

2번 학생들을 배치 할 순서 는 Student라는 int형 벡터를 만들어서 입력되는 순서대로 학생들의 번호를 저장했다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.​

위의 조건을 순서대로 적용시키면 된다.

1번 조건에 따라 먼저 모든 칸을 돌면서 해당 칸이 빈칸이면, 해당칸에 대해서 인접한 칸(4칸) 중 현재 자리에 앉을 학생( i 학생)이 좋아하는 학생이 가장 많은 칸들의 인덱스를 Where이라는 벡터에 저장해둔다.

이때, 만약 Where 벡터의 크기가 1이면 들어갈 자리가 하나뿐이라는 뜻이므로 해당 인덱스에 i 학생을 앉힌다.

Where 벡터의 크기가 2이상이라면 2번 조건을 적용시켜야한다.

2번 조건에 따라 Where에 들어있는 인덱스를 돌면서 인접한 칸 중 빈칸이 가장 많은 자리의 인덱스를 다시 한 번 Where 벡터에 넣는다.

물론 이때 기존에 Where에 들어있던 값은 빼주고 새로운 값만 넣어주어야한다. 그래서 나는 Temp라는 벡터에 인접 칸 중 빈칸이 가장 많은 인덱스를 넣어두고 마지막에 Where = Temp 라고 해줬다.

2번 조건을 적용시킨 후 Where 벡터의 크기가 1이면 해당 자리에 i 학생을 앉힌다.

Where 벡터의 크기가 2이상이라면 3번 조건에 따라 Where 벡터를 정렬해준 후 가장 앞에있는 인덱스에 i 학생을 앉히면 끝.

이렇게 모든 학생들을 앉게하고 나서 모든 칸을 돌면서 해당 학생들의 만족도를 ans라는 변수에 더해줬다.

마지막에 ans를 출력해주면 끝이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 400 + 5;
int N, Q;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
vector<int> Like[MAX_N];
vector<int> Student;
int A[MAX_N][MAX_N];
vector<pair<int, int>> Where;
 
bool is_ok(pair<int, int>);
void num_one(int std);
void num_two();
bool is_like(int std, int like);
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 1; i <= N * N; i++) {
        int Std;
        cin >> Std;
        Student.push_back(Std);
        for (int j = 0; j < 4; j++) {
            int like; cin >> like;
            Like[Std].push_back(like);
        }
    }
    for (int i = 0; i < Student.size(); i++) {
        Where.clear();
        int now = Student[i];
        num_one(now);
        if (Where.size() == 1) {
            A[Where[0].first][Where[0].second] = now;
            continue;
        }
        num_two();
        if (Where.size() == 1) {
            A[Where[0].first][Where[0].second] = now;
            continue;
        }
            sort(Where.begin(), Where.end());
            A[Where[0].first][Where[0].second] = now;
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int now = A[i][j];
            int cnt = 0;
            for (int k = 0; k < 4; k++) {
                pair<int, int> next = { i + dy[k], j + dx[k] };
                if (is_ok(next) && is_like(now, A[next.first][next.second]))
                    cnt++;
            }
            if (cnt == 0)
                continue;
            ans += (int)pow(10, cnt - 1);
        }
    }
    cout << ans << "\n";
    return 0;
}
 
void num_one(int std) {
    int Max = -1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (A[i][j])
                continue;
            int cnt = 0;
            for (int k = 0; k < 4; k++) {
                pair<int, int> next = { i + dy[k], j + dx[k] };
                if (is_ok(next) && is_like(std, A[next.first][next.second]))
                    cnt++;
            }
            if (cnt > Max) {
                Max = cnt;
                Where.clear();
                Where.push_back({ i,j });
            }
            else if (cnt == Max)
                Where.push_back({ i,j });
        }
    }
}
 
void num_two() {
    int Max = -1;
    vector<pair<int,int>> temp;
    for (int i = 0; i < Where.size(); i++) {
        pair<int, int> now = Where[i];
        int cnt = 0;
        for (int j = 0; j < 4; j++) {
            pair<int, int> next = { now.first + dy[j], now.second + dx[j] };
            if (is_ok(next) && !A[next.first][next.second])
                cnt++;
        }
        if (cnt > Max) {
            Max = cnt;
            temp.clear();
            temp.push_back(now);
        }
        else if (cnt == Max)
            temp.push_back(now);
    }
    Where = temp;
}
 
bool is_like(int std, int like) {
    for (int i = 0; i < Like[std].size(); i++) {
        if (Like[std][i] == like)
            return true;
    }
    return false;
}
 
bool is_ok(pair<int, int> now) {
    if (now.first < 1 || now.first > N || now.second < 1 || now.second > N)
        return false;
    return true;
}

 여기서 좋아하는 학생인지 아닌지를 이차원 bool 배열을 이용해서 표현한다면, 

예를들어 bool is_like[ i ][ j ] 가 true면 i가 j를 좋아하는다는 뜻이다.

이렇게 하면 학생 i가 학생 j를 좋아하는지를 O(1)만에 판별할 수 있다.

기존의 내 코드는 i가 좋아하는 학생들의 목록에 j가 들어있는지 판단하므로 최대 O(4) 만큼의 시간이 걸린다.

대신 bool 이차원 배열을 선언해야하므로 메모리가 조금 더 쓰일 것같다.