[백준/구현/C++] 21608번 상어 초등학교 (삼성 SW 역량 테스트 기출) *

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

21608번: 상어 초등학교

일단 머리로 시뮬레이션을 돌려봤는데 내가 생각한 방법으로는 무조건 시간초과가 나올 것 같아서 블로그를 참조했다.

https://yabmoons.tistory.com/656 이 블로그를 봤는데 생각도 못한 구조체랑 필요에 맞게 조건을 만들어서 정렬하는 등 배울게 많았다. 다시 풀어보면서 공부해야겠다.

 

문제 해결 방법

먼저 구조체 두개를 선언한다

학생정보(STUDENT), 자리 배치를 위해 알아야 할 정보(POSITION)

struct STUDENT // 학생정보
{
    int Num; // 학생 번호
    int Friend[4]; // 좋아하는 학생
};

struct POSITION // 자리 배치를 위해 알아야 할 정보
{
    int x; // 현재 칸의 x좌표
    int y; // 현재 칸의 y좌표
    int Nearly_Empty; // 인접한 칸에 존재하는 빈칸의 수
    int Nearly_Friend; // 인접한 칸에 존재하는 좋아하는 학생의 수
};

필요한 변수들을 선언하고 입력을 받는다

student_arr[] 배열은 학생들의 번호 순서대로 정보를 입력받은 것이고

벡터 student는 탐색할 순서대로 입력을 받은 것이다

int n, answer;
int MAP[MAX][MAX];
STUDENT student_arr[MAX*MAX];
vector<STUDENT> student;

void input(){
    cin >> n;
    for(int i=0; i<n*n; i++){
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        student.push_back({a, {b, c, d, e}});
        student_arr[a].Num = a;
        student_arr[a].Friend[0] = b;
        student_arr[a].Friend[1] = c;
        student_arr[a].Friend[2] = d;
        student_arr[a].Friend[3] = e;
    }
}

벡터에 입력된 순서대로 학생마다 자리를 배치해준다

void Set_Position(){ // 자리 배치하기
    for(int i=0; i<student.size(); i++){
        vector<POSITION> pos;// i번째 학생 입장에서 각 자리의 정보
        int Student_Num = student[i].Num;

        for(int x=0; x<n; x++){
            for(int y=0; y<n; y++){
                if(MAP[x][y] != 0) continue; // 자리 차지하고 있으면 통과

                int Nearly_Friend = 0;
                int Nearly_Empty = 0;

                for(int k=0; k<4; k++){ // 상하좌우 탐색
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if(nx<0 || ny <0 || nx>=n|| ny>=n) continue;
                    if(MAP[nx][ny] == 0) Nearly_Empty++; // 인접한 빈칸인 경우
                    else { // 빈칸이 아닌 경우
                        for(int j=0; j<4; j++){
                            int Friend_Num = student[i].Friend[j];
                            if(MAP[nx][ny] == Friend_Num){ // 인접한 칸에 좋아하는 친구인 경우
                                Nearly_Friend++;
                                break;
                            }
                        }
                    }
                }
                pos.push_back({x, y, Nearly_Empty, Nearly_Friend});
            }
        }
        sort(pos.begin(), pos.end(), cmp); // 자리배치 조건으로 정렬
        int Pos_x = pos[0].x;
        int Pos_y = pos[0].y;
        MAP[Pos_x][Pos_y] = Student_Num; // 최적의 자리에 배치
    }
}

최적의 자리를 찾기위해 사용하는 정렬은 아래의 조건을 사용한다

bool cmp(POSITION A, POSITION B){ // 자리배치 조건
    if(A.Nearly_Friend >= B.Nearly_Friend){ // 좋아하는 친구가 더 많으면  true
        if(A.Nearly_Friend == B.Nearly_Friend){ // 좋아하는 친구 같고 빈칸 더 적으면 false
            if(A.Nearly_Empty >= B.Nearly_Empty){ // 비어있는 칸 수 더 많으면 true
                if(A.Nearly_Empty == B.Nearly_Empty){ // 비어있는 칸 수 같고 행값 더 크면 fasle
                    if(A.x <= B.x){ // 행값이 더 작으면 true
                        if(A.x == B.x){ // 행값이 같고 열값 더 크거나 같으면 false
                            if(A.y < B.y){ // 열값이 더 작으면 true
                                return true;
                            }
                            return false;
                        }
                        return true;
                    }
                    return false;
                }
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}

만족도 조사에서는 아까 선언한 배열을 사용하여 구해준다

int calculate(int f){
    if(f==0) return 0;
    if(f==1) return 1;
    if(f==2) return 10;
    if(f==3) return 100;
    if(f==4) return 1000;
}
// 만족도 조사
void calculate_satisfy(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int student_num = MAP[i][j]; // (i,j) 위치의 학생 번호
            int Friend = 0;
            for(int k=0; k<4; k++){ // 상하좌우 탐색
                int nx = i + dx[k];
                int ny = j + dy[k];
                if(nx<0 || ny<0 || nx>= n || ny>=n) continue;

                for(int l=0; l<4; l++){
                    int friend_num = student_arr[student_num].Friend[l];
                    if(MAP[nx][ny] == friend_num){ // 좋아하는 친구인 경우
                        Friend++;
                        break;
                    }
                }
            }
            answer += calculate(Friend); // 만족도 계산
        }
    }
}

 

전체 코드

#include <bits/stdc++.h>

#define MAX 21
using namespace std;

struct STUDENT // 학생정보
{
    int Num; // 학생 번호
    int Friend[4]; // 좋아하는 학생
};

struct POSITION // 자리 배치를 위해 알아야 할 정보
{
    int x; // 현재 칸의 x좌표
    int y; // 현재 칸의 y좌표
    int Nearly_Empty; // 인접한 칸에 존재하는 빈칸의 수
    int Nearly_Friend; // 인접한 칸에 존재하는 좋아하는 학생의 수
};

int n, answer;
int MAP[MAX][MAX];
STUDENT student_arr[MAX*MAX];
vector<STUDENT> student;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void input(){
    cin >> n;
    for(int i=0; i<n*n; i++){
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        student.push_back({a, {b, c, d, e}});
        student_arr[a].Num = a;
        student_arr[a].Friend[0] = b;
        student_arr[a].Friend[1] = c;
        student_arr[a].Friend[2] = d;
        student_arr[a].Friend[3] = e;
    }
}

bool cmp(POSITION A, POSITION B){ // 자리배치 조건
    if(A.Nearly_Friend >= B.Nearly_Friend){ // 좋아하는 친구가 더 많으면  true
        if(A.Nearly_Friend == B.Nearly_Friend){ // 좋아하는 친구 같고 빈칸 더 적으면 false
            if(A.Nearly_Empty >= B.Nearly_Empty){ // 비어있는 칸 수 더 많으면 true
                if(A.Nearly_Empty == B.Nearly_Empty){ // 비어있는 칸 수 같고 행값 더 크면 fasle
                    if(A.x <= B.x){ // 행값이 더 작으면 true
                        if(A.x == B.x){ // 행값이 같고 열값 더 크거나 같으면 false
                            if(A.y < B.y){ // 열값이 더 작으면 true
                                return true;
                            }
                            return false;
                        }
                        return true;
                    }
                    return false;
                }
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}

void Set_Position(){ // 자리 배치하기
    for(int i=0; i<student.size(); i++){
        vector<POSITION> pos;// i번째 학생 입장에서 각 자리의 정보
        int Student_Num = student[i].Num;

        for(int x=0; x<n; x++){
            for(int y=0; y<n; y++){
                if(MAP[x][y] != 0) continue; // 자리 차지하고 있으면 통과

                int Nearly_Friend = 0;
                int Nearly_Empty = 0;

                for(int k=0; k<4; k++){ // 상하좌우 탐색
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if(nx<0 || ny <0 || nx>=n|| ny>=n) continue;
                    if(MAP[nx][ny] == 0) Nearly_Empty++; // 인접한 빈칸인 경우
                    else { // 빈칸이 아닌 경우
                        for(int j=0; j<4; j++){
                            int Friend_Num = student[i].Friend[j];
                            if(MAP[nx][ny] == Friend_Num){ // 인접한 칸에 좋아하는 친구인 경우
                                Nearly_Friend++;
                                break;
                            }
                        }
                    }
                }
                pos.push_back({x, y, Nearly_Empty, Nearly_Friend});
            }
        }
        sort(pos.begin(), pos.end(), cmp); // 자리배치 조건으로 정렬
        int Pos_x = pos[0].x;
        int Pos_y = pos[0].y;
        MAP[Pos_x][Pos_y] = Student_Num; // 최적의 자리에 배치
    }
}

int calculate(int f){
    if(f==0) return 0;
    if(f==1) return 1;
    if(f==2) return 10;
    if(f==3) return 100;
    if(f==4) return 1000;
}
// 만족도 조사
void calculate_satisfy(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int student_num = MAP[i][j]; // (i,j) 위치의 학생 번호
            int Friend = 0;
            for(int k=0; k<4; k++){ // 상하좌우 탐색
                int nx = i + dx[k];
                int ny = j + dy[k];
                if(nx<0 || ny<0 || nx>= n || ny>=n) continue;

                for(int l=0; l<4; l++){
                    int friend_num = student_arr[student_num].Friend[l];
                    if(MAP[nx][ny] == friend_num){ // 좋아하는 친구인 경우
                        Friend++;
                        break;
                    }
                }
            }
            answer += calculate(Friend); // 만족도 계산
        }
    }
}


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

    input();
    Set_Position();
    calculate_satisfy();
    cout << answer;

    return 0;
}

 

출처

https://yabmoons.tistory.com/656