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

문제

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

백준 21608

백준 21608

백준 2108

 

문제 내용

N*N명의 학생이 N*N 크기의 격자에 아래 방법대로 앉는다. (격자는 (1,1)부터 (N,N)까지이다.)

각 학생별로 그 학생이 좋아하는 학생들 4명이 입력으로 주어진다.

|r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.

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

위 방법에 따라 학생들의 자리를 배치한 뒤, 각 학생별로 만족도를 계산하면 된다.

인접한 칸에 앉은 좋아하는 친구의 수가 0이면 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

각 학생의 만족도를 모두 더한 값을 출력하자.

 

문제 풀이

처음에는 막막해 보이지만, 차례대로 구현해 나가면 된다.

N의 크기가 20까지로 작기 때문에 브루트포스로 풀어도 된다.

|r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸은 무조건 상하좌우만 가능하다.

 

일단 학생을 순서대로 앉혀야 한다. 아래의 로직에 따라 앉히면 된다.

1. 일단 자리에 앉힐 학생의 번호와, 그 학생이 좋아하는 친구 4명을 입력받는다.

2. 앉힐 자리를 탐색하여 앉힌다.

  2-1) 비어있는 칸들의 "인접한 좋아하는 학생들 수"를 모두 구한다. 그리고, 그중에 가장 큰 값을 가지는 칸들만 벡터에 담아둔다.

  2-2) 2-1에서 만들어진 벡터들에서 해당 칸의 "인접한 공백들 수"를 모두 구한다. 그리고, 그중에 가장 큰 값을 가지는 칸들만 벡터에 담는다.

  2-3) 2-2에서 만든 벡터를 정렬하면 가장 앞의 원소가 문제에서 주어진 3번 조건을 만족하는 칸이다. 해당 칸에 1번에서 입력받은 학생의 번호를 넣으면 된다.
(3번 조건: 값이 같으면 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개면 열의 번호가 가장 작은 칸으로)

1,2번을 모든 학생들에 대해 반복한다.

그리고 모든 학생에 대해 만족도를 계산한 후에 더하여 출력하면 된다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int arr[401][4]={0,};
int seat[21][21]={0,};

int dr[4]={-1,1,0,0};
int dc[4]={0,0,1,-1};

/* student가 seatStudent를 좋아하는지 체크
 * student가 좋아하는 친구 목록에 seatStudent가 있는지 확인할 것
 */
bool isLikeStudent(int student, int seatStudent){
    for(int i=0;i<4;i++){
        if(arr[student][i]==seatStudent) return true;
    }
    return false;
}

//특정 칸(r,c)을 기준으로 상하좌우를 탐색하여, student가 좋아하는 사람 수 구하기
int returnLikeFriend(int r,int c, int student){
    int friendCnt=0;
    for(int i=0;i<4;i++){
        int nr=r+dr[i];
        int nc=c+dc[i];
        
        if(nr>=1 && nr<=n && nc>=1 && nc<=n){
            if(isLikeStudent(student, seat[nr][nc])){
                friendCnt++;
            }
        }
    }
    return friendCnt;
}

//특정 칸(r,c)을 기준으로 상하좌우를 탐색하여, 공백 개수 구하기
int returnBlank(int r,int c){
    int blank=0;
    for(int i=0;i<4;i++){
        int nr=r+dr[i];
        int nc=c+dc[i];
        
        if(nr>=1 && nr<=n && nc>=1 && nc<=n){
            if(seat[nr][nc]==0) blank++;
        }
    }
    return blank;
}

// 자리 결정
void decideSeat(int student){
    //만족도가 최대인 자리 구하기
    int seat_like=-1;
    vector<pair<int,int>> like_list; //만족도가 최대인 위치들 리스트
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(seat[i][j]==0){
                int like_cnt=returnLikeFriend(i,j,student);
                if(like_cnt>seat_like){ //만족도 갱신
                    like_list.clear();
                    like_list.push_back({i,j});
                    seat_like=like_cnt;
                }else if(like_cnt==seat_like){ //만족도 리스트에 추가
                    like_list.push_back({i,j});
                }
            }
        }
    }
    
    //공백 최대인 곳 구하기
    int seat_blank=-1;
    vector<pair<int,int>> blank_list; //공백 최대인 곳들 리스트
    
    for(int i=0;i<like_list.size();i++){
        int blank_cnt=returnBlank(like_list[i].first, like_list[i].second);
        if(blank_cnt>seat_blank){
            blank_list.clear();
            blank_list.push_back(like_list[i]);
            seat_blank=blank_cnt;
        }else if(blank_cnt==seat_blank){
            blank_list.push_back(like_list[i]);
        }
    }
    
    // sort함수: 첫번째 인자(행) 기준으로 정렬 후, 같은 경우 두번째 인자(열) 기준으로 정렬
    sort(blank_list.begin(), blank_list.end());
    pair<int,int> seat_result=blank_list[0];
    seat[seat_result.first][seat_result.second]=student;
    return ;
}


// (r,c)위치의 학생 만족도 구하기
int calcLikeScore(int r, int c){
    int cnt=returnLikeFriend(r,c, seat[r][c]);
    
    switch(cnt){
        case 0 : return 0;
        case 1: return 1;
        case 2: return 10;
        case 3: return 100;
        default: return 1000;
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    
    int student;
    for(int i=1;i<=n*n;i++){
        cin>>student;
        for(int i=0;i<4;i++){ //student 학생의 좋아하는 친구 저장 
            cin>>arr[student][i];
        }
        
        decideSeat(student); 
    }
    
    // 모든 학생의 만족도 계산
    int like_score=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            like_score+=calcLikeScore(i,j);
        }
    }
    cout<< like_score;
}

 

문제 코드 설명

decideSeat()에서 최대 만족도를 구하는 부분과 최대 공백 개수를 구하는 부분에서 seat_like와 seat_blank의 초기값을 -1로 설정해 두었다.

왜냐하면 저렇게 해두어야 1) 인접한 칸에 좋아하는 친구가 아무도 없는 경우 or 2) 인접한 칸에 공백이 없는 경우도 포함할 수 있기 때문이다. 

1)의 예시로는 맨 처음에 모든 자리가 비어있을 때가 있다. (맨 처음이 아니어도 seat_like가 0인 상황이 발생할 수 있다.)

2)의 예시로는 맨 마지막에 모든 자리가 차고, 단 한 자리만 남았을 경우이다. (맨 마지막이 아니어도 seat_blank가 0인 상황이 발생할 수 있다.)