[백준 21608][C++] 상어 초등학교

문제

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

21608번: 상어 초등학교

 

풀이 과정

1. 주변을 탐색해서 인접한 칸의 좋아하는 학생의 수를 반환하는 함수 구현

2. 주변을 탐색해서 인접한 칸의 빈칸의 수를 반환하는 함수 구현

3. 1을 이용하여 좋아하는 학생의 수가 같은 경우가 여러 개 있다면 2를 수행하여 학생의 위치를 정한다.

4. 위의 함수를 이용하여 학생들의 자리를 모두 배치한다.

5. 배치가 완료된 상태에서의 각 학생들의 만족도를 구하여 출력한다.

 

 

세부 풀이

(1) num_prefer 함수

4방향을 탐색한다. 입력 시 받았던 선호 학생들과 비교하며 cnt를 증가시키며 기록된 cnt 값을 반환한다.

 

(2) num_blank 함수

4방향을 탐색한다. 현재 map에서 빈칸인 경우의 수를 구하여 반환한다.

 

(3) seat 함수

같은 선호 학생 수를 갖는 경우를 표현하기 위해 vector를 구현하여 저장했다.

 

num_prefer 함수를 이용하여 해당 칸에서의 선호 학생 수를 구한다. 이 값이 현재 기록되어있는 max값 보다 크다면 vector를 초기화하고 현재 값을 push 한다. max값과 같다면 vector에 추가한다.

 

위 과정을 통해 최종적으로 선호 학생이 가장 많은 자리가 vector에 추가된 상태이다. 현재 vector의 사이즈가 1이라면 선호 학생이 가장 많은 자리가 하나이므로 바로 업데이트하고, 그렇지 않은 경우 num_blank 함수를 이용하여 vector를 탐색한다.

 

vector를 탐색하며 인접한 빈칸의 수가 큰 경우 업데이트를 수행한다. 이처럼 구현하면 문제에서 주어진 '2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.' 조건을 만족시킬 수 있다. 행열 순서로 탐색하며 큰 값일 경우에만 업데이트했으므로 같은 값들을 가지는 값들 중 가장 먼저 등장한 위치의 값이 저장되게 된다. 따라서 조건을 만족시키며 탐색을 진행할 수 있다.

 

num_prefer 함수와 num_blank 함수를 이용하여 탐색할 때 이미 학생이 있는 자리라면(값이 0이 아니라면) 건너뛰도록 구현해야 한다. 그렇지 않을 경우 문제의 예시와 같은 경우에서 계속 4번 학생의 위치에 새로운 값이 업데이트 되게 된다.

 

(4) (5) solve 함수 / score 함수

seat 함수를 입력받은 학생의 순서대로 실행한 뒤 모두 자리를 배치한다. 이후 score 함수를 통해 최종 만족도 점수를 구한 뒤 출력한다.

 

소스 코드

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

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int N, ans;
const int max_n = 21;
int map[max_n][max_n];
int prefer[max_n*max_n][4];
vector<int> order;

void Input(){
    cin >> N;
    for(int i=0;i<N*N;i++){
        int idx; cin >> idx;
        order.push_back(idx);
        for(int j=0;j<4;j++){
            cin >> prefer[idx][j];
        }
    }
}

bool out_range(int x, int y){
    return x<0 || x>=N || y<0 || y>=N;
}

int num_prefer(int s, int x, int y){
    int cnt=0;
    for(int i=0;i<4;i++){
        int nx = x+dir[i][0];
        int ny = y+dir[i][1];
        if(out_range(nx,ny)) continue;
        for(int j=0;j<4;j++){
            if(map[nx][ny]==prefer[s][j]) cnt++;
        }
    }

    return cnt;
}

int num_blank(int x, int y){
    int cnt=0;
    for(int i=0;i<4;i++){
        int nx = x+dir[i][0];
        int ny = y+dir[i][1];
        if(out_range(nx,ny)) continue;
        for(int j=0;j<4;j++){
            if(map[nx][ny]==0) cnt++;
        }
    }

    return cnt;
}

void seat(int s){
    int max_cnt=0;
    vector<pair<int,int>> v;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]!=0) continue;
            int value = num_prefer(s,i,j);
            if(max_cnt<value){
                max_cnt = value;
                v.clear();
                v.push_back({i,j});
            }
            if(max_cnt==value){
                v.push_back({i,j});
            }
        }
    }

    if(v.size()==1){
        map[v[0].first][v[0].second]=s;
        return;
    }

    //열 행 순서로 탐색했으니 벡터에도 그 순서대로 들어있다.
    int max_blank_cnt=-1;
    int x, y;

    for(int i=0;i<v.size();i++){
        int temp_x=v[i].first;
        int temp_y=v[i].second;
        if(map[temp_x][temp_y]!=0) continue;
        int value = num_blank(temp_x,temp_y);
        if(max_blank_cnt<value){
            max_blank_cnt = value;
            x=temp_x;
            y=temp_y;
        }
    }
    map[x][y]=s;
}


void score(int max_cnt){
    switch (max_cnt){
        case 1:
            ans+=1;
            break;
        case 2:
            ans+=10;
            break;
        case 3:
            ans+=100;
            break;
        case 4:
            ans+=1000;
            break;
        default:
            break;
    }
}

void solve(){
    for(int i=0;i<order.size();i++){
        int s = order[i];
        seat(s);
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int value = num_prefer(map[i][j],i,j);
            score(value);
        }
    }
    cout << ans;
}

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

    Input();
    solve();


    return 0;
}

 

결과 및 후기

제출 이후 다른 사람의 코드를 둘러보던 중 [링크] 와 같은 코드를 발견했다. 해당 코드는 문제에서 주어진 논리를 모두 담고 있음에도 bool 연산과 배열 if 문 만으로 간결하고 깔끔하게 표현했다. 정말 효율적으로 구현된 것 같다. 다른 코드들도 깔끔하고 더 메모리를 절약한 코드들도 있었지만 위 링크의 코드에서처럼 구현할 생각을 하지 못했을 것 같아 링크로 남겨보았다.