BOJ 21608(상어 초등학교)

📜 문제

문제링크
시뮬레이션 문제로 문제에서 주어진 조건을 구현하기만 하면 된다.

📖 풀이

문제의 조건을 읽어보면 현재 관찰하는 영역을 기준으로 (비어 있는 칸)

1) 인접한 영역에 좋아하는 학생의 수
2) 인접한 영역에 비어있는 영역의 수
3) 관찰하는 영역의 (r , c)

총 3가지를 저장하는 공간이 필요한 것을 알 수 있다. 이를 비어 있는 모든 칸에 대해서 수행하고 나면 현재 자리를 배치할 학생의 가능한 모든 자리에 대해서 위의 3가지가 저장되게 된다. 그리고 이를 문제의 조건에 맞게 정렬하면 현재 관찰하는 학생의 자리를 확정할 수 있다.

1. 공간복잡도

   1) 각 학생별로 선호하는 학생을 저장 할 배열 int[400][4]
   2) 각 학생의 위치를 저장할 board 배열 int[20][20]
   3) 위의 세가지를 저장할 vector int[20][20] x4

3)의 경우에 pair 를 이용해 pair<int,pair<int,pair<int,int>>>> 형태로 저장
메모리 제한이 1024Mb로 약 2.4억개의 int 를 사용할 수 있기 때문에 메모리 초과는 발생하지 않는다.

2. 시간복잡도

   1) 해당 학생의 가능한 모든 자리를 조사 O(N^2)
   2) 해당 학생의 가능한 모든 자리를 정렬 O(N^2)
   3) 자리를 모두 결정하고 점수를 매기는 과정 O(N^2)

최악의 경우를 기준으로 생각해보자
학생들의 자리가 배정됨에 따라 1), 2) 과정의 시간복잡도는 줄어들겠지만 계산상의 편의를 위해 모든 학생들의 자리 배정이 위의 시간복잡도를 따른다고 해보자.
N^2 * O(N^2) = O(N^4) 이지만 N의 최대값이 20이기 때문에 1초내에 통과 할 수 있다.

🖥 코드

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

int n,answer;
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
int prefer[404][4];
int board[22][22];

//인접한 칸에 좋아하는 학생수, 인접한 칸에 비어있는 칸, {행,열} 를 문제의 조건에 맞게 정렬하기 위한 compare 함수
bool compare(pair<int,pair<int,pair<int,int>>>v1, pair<int,pair<int,pair<int,int>>>v2){
    if(v1.first == v2.first){
        if(v1.second.first == v2.second.first){
            if(v1.second.second.first == v2.second.second.first){
                return v1.second.second.second < v2.second.second.second;
            }
            return v1.second.second.first < v2.second.second.first;
        }
        else return v1.second.first > v2.second.first;
    }
    else return v1.first > v2.first;
}

void student_position(int num){
    //인접한 칸에 좋아하는 학생수, 인접한 칸에 비어있는 칸, {행,열} 순서로 저장
    vector<pair<int,pair<int,pair<int,int>>>>v;
    for(int y=0; y<n; y++){
        for(int x=0; x<n; x++){
            if(board[y][x]!=0)continue;
            int first=0,second=0;
            //인접한 영역을 돌면서 좋아하는 학생수, 비어있는 칸의 개수를 센다.
            for(int dir=0; dir<4; dir++){
                int ny=y+dy[dir];
                int nx=x+dx[dir];
                if(ny<0 || ny>=n || nx<0 || nx>=n)continue;
                if(board[ny][nx]==0)second++;
                else{
                    for(int i=0; i<4; i++){
                        int prefer_student=prefer[num][i];
                        if(board[ny][nx]==prefer_student)first++;
                    }
                }
            }
            v.push_back({first,{second,{y,x}}});
        }
    }
    sort(v.begin(),v.end(),compare);
    int y=v[0].second.second.first;
    int x=v[0].second.second.second;
    board[y][x]=num;//조건에 맞는 위치에 학생을 배치한다.
}

//학생들이 모두 앉았을때 점수를 구하기 위한 함수
void make_answer(){
    for(int y=0; y<n; y++){
        for(int x=0; x<n; x++){
            int num=board[y][x];
            int cnt=0;
            for(int dir=0; dir<4; dir++){
                int ny=y+dy[dir];
                int nx=x+dx[dir];
                if(ny<0 || ny>=n || nx<0 || nx>=n)continue;
                for(int i=0; i<4; i++){
                    if(board[ny][nx]==prefer[num][i])cnt++;
                }
            }
            if(cnt==0)continue;
            else if(cnt==1)answer+=1;
            else if(cnt==2)answer+=10;
            else if(cnt==3)answer+=100;
            else answer+=1000;
        }
    }
}

int main(void){

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=1; i<=n*n; i++){
        int num;
        cin>>num;
        for(int j=0; j<4; j++){
            cin>>prefer[num][j];
        }
        student_position(num);
    }
    make_answer();
    cout<<answer;

    return 0;
}

🔨 피드백

처음 문제를 읽었을 때, 정렬을 이용하면 문제를 쉽게 해결할 수 있겠다라는 생각은 들었지만 막상 sort 함수의 cmp 함수를 만드는 과정에서 조금 시간이 걸렸다.

bool cmp1(int a, int b){
    return a>b;
}

bool cmp2(int a, int b){
    if(a>b) return true;
    else return false;
}

위의 두 cmp 함수는 a가 b보다 클 때 우선적으로 정렬을 하겠다는 것을 의미한다. 그리고 이번 문제를 풀기 위해서 선언했던 cmp 함수를 살펴보자!

bool compare(pair<int,pair<int,pair<int,int>>>v1, pair<int,pair<int,pair<int,int>>>v2){
    if(v1.first == v2.first){
        if(v1.second.first == v2.second.first){
            if(v1.second.second.first == v2.second.second.first){
                return v1.second.second.second < v2.second.second.second;
            }
            return v1.second.second.first < v2.second.second.first;
        }
        else return v1.second.first > v2.second.first;
    }
    else return v1.first > v2.first;
}

위의 경우를 살펴보면 현재 살펴보는 칸과 인접한 영역에 좋아하는 학생의 수가 큰 경우 우선적으로 정렬하고, 만약 같다면 인접한 영역에 비어있는 칸 수 가 큰 경우 우선적으로 정렬하고 , 마찬가지로 비어 있는 칸수가 같으면 행, 열 순서대로 살피도록 설정했다.

문제 자체의 풀이는 조건 그대로를 구현하면 되기 때문에 다른 문제들에 비해서 쉽게 느껴졌지만 항상 정렬에서 cmp를 만드는 부분이 헷갈리는 것 같다! 관련 문제들 풀어보면서 확실하게 개념공부 해야겠다!🔥