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

백준의 상어초등학교(21608) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 조건에 맞게 학생들을 배치했을 때, 학생들의 만족도를 구해야 하는 문제이다.

주어진 정보들을 관리하는 과정부터 정답을 도출하는 과정까지 순차적으로 진행해보자.

 

#1. 입력 데이터 관리

우리에게 입력 데이터로는 "학생의 번호 & 해당 학생이 좋아하는 4명의 학생" 이 주어지게 된다.

그래서 본인은 이 2가지 정보를 관리하기 위해서 다음과 같은 구조체를 하나 선언해서 관리해 주었다.

struct STUDENT
{
	int Num;
	int Friend[4];
};

위와 같이 2개의 멤버변수를 가지는 구조체를 선언해 주었다.

그리고, 이제부터 이 구조체를 자료형으로 가지는 변수들을 선언할 것이다.

본인은 이 입력으로 들어오는 데이터들을 다음과 같은 2개의 변수에 저장해 주었다.

1. 구조체 'STUDENT'를 자료형으로 가지는 Vector

2. 구조체 'STUDENT'를 자료형으로 가지는 Array

위와 같이 Vector로 하나, 배열로 하나 총 2개를 선언해서 입력 데이터들을 저장해 주었다.

struct STUDENT
{
	int Num;
	int Friend[4];
};

STUDENT Student_Arr[MAX * MAX];
vector<STUDENT> Student;

그렇다면 ! 왜 Vector도 필요하고 Array도 필요할까 ??? 이 부분에 대해서는 아래쪽에서 보다 구체적으로 알아보도록 하자.

지금부터 메인처럼 사용할 변수는 'Vector'이다. 배열은 나중에 잠깐만 사용할 것이다.

위와 같이 Vector를 선언해서 주어진 정보들을 저장시켰다면 다음 단계로 넘어가보자.

# 입력 데이터를 관리하기 위한 구조체  STUDENT 를 선언해서 관리.
# 정확한 용도는 모르겠지만, STUDENT를 자료형으로 가지는 Vector와 Array 각각 선언해서 총 2개의 변수에 저장.

 

#2. 자리 배치를 위한 정보

이제부터는 입력 데이터가 저장되어 있는 Vector를 통해서 실제로 자리를 배치해볼 것이다.

자리를 배치해보기 전에 자리 배치를 하기 위한 조건들 부터 다시 한번 체크해보자.

1. 빈 칸 중에서, 좋아하는 학생이 인접한 칸에 많은 곳으로 1차적으로 배치.

2. 1번 조건을 여러 칸이 만족한다면, 인접한 칸에 빈 칸이 많은 곳으로 2차적으로 배치.

3. 2번 조건을 여러 칸이 만족한다면, 행이 가장 작은 칸으로 3차적으로 배치.

4. 3번 조건을 여러 칸이 만족한다면, 열이 가장 작은 칸으로 최종적으로 배치.

 

그렇다면 위의 4가지 조건을 만족시키기 위해서 우리가 알고 있어야 할 정보가 어떤 것들이 있는지 부터 파악해보자.

1. 현재 칸으로 부터 인접한 칸에 좋아하는 학생이 얼마나 있는지에 대한 정보가 필요할 것이다.

     즉 ! "인접한 칸에 존재하는 좋아하는 학생의 수" 가 필요할 것이다.

2. 현재 칸으로 부터 인접한 칸에 빈 칸이 얼마나 있는지에 대한 정보가 필요할 것이다.

     즉 ! "인접한 칸에 존재하는 빈칸의 수" 가 필요할 것이다.

3. 현재 칸의 행과 열, 즉 ! "현재 칸의 (x , y)좌표"가 각각 필요할 것이다.

우리가 자리 배치를 위해서 알고 있어야 할 정보는 위에서 설명한 4가지 정보이다. (행과 열은 각각 취급해서 총 4가지)

이를 관리하기 위해서 또 하나의 구조체를 선언해 주었다.

struct POSITION
{
	int x;
	int y;
	int Nearly_Empty;
	int Nearly_Friend;
};

위와 같이 "자리 배치를 위해서 알아야 할 정보들을 구조체로 선언" 해 주었다.

그리고 해당 구조체를 자료형으로 가지는 Vector를 하나 선언해 주었다.

이 Vector를 어떻게 활용할지는 다음 단계에서 부터 구체적으로 알아보자.

 

그리고 ! "인접한 칸" 이라는 단어가 자주 나오고, 문제에서 "인접한 칸"이 어떻게 계산되는지 주어졌지만, 보다 간단하게 이야기해보면, 현재 좌표를 기준으로 상/하/좌/우 4칸이 문제에서 설명하는 "인접한 칸"이 된다.

우리가 최종적으로 구해야 하는 만족도를 보면, "0 = 1 , 1 = 1 , 2 = 10 , 3 = 100 , 4 = 1000" 이라고 되어있는데, 이를 통해서도 인접한 칸은 총 4칸만 존재한다는 것을 눈치챌 수 있다.

자리 배치를 위해 알아야할 정보와 이 정보들을 어떻게 관리할지에 대해서 까지 알았으면 실제로 자리를 배치하는 단계로 넘어가보자.

# 자리 배치를 위해 필요한 정보들을 구조체 'POSITION'으로 만들어서 관리.
# 이 구조체를 자료형으로 가지는 Vector를 선언해서 실제로 자리를 배치할 것이다.

 

#3. 자리 배치하기

이제 자리를 배치해보자. 자리를 배치해보기 전에, 우리는 "입력 데이터로 주어진 "순.서.대.로" 자리를 배치"해 주어야 한다.

그리고 우리는 입력 데이터를 #1에서 'STUDENT'를 자료형으로 가지는 Vector를 하나 선언해 주었다.

그렇다면 ! 이 Vector에는 "입력데이터의 순서대로" 데이터가 삽입되어 있을 것이다. 따라서, 우리는 이 Vector를 기반으로 자리를 배치할 것이다.

자리 배치를 위해 #2에서 'POSITION' 구조체를 자료형으로 가지는 Vector를 하나 선언해 주었다.

우리는 지금부터 이 Vector에 모든 좌표들에 대한 정보를 모두 저장할 것이다. 물론 ! 이미 자리배치가 완료되어 누군가가 앉아있는 자리에 대해서는 정보를 구할 필요가 없을 것이다.

빈 칸에 한해서, 해당 빈칸이 주어진 조건을 얼마나 만족하는지를 파악하기 위해서 #2에서 구한 4가지 정보를 저장할 것이다.

코드로 표현하면 다음과 같다.

for (int i = 0; i < Student.size(); i++)
{
	vector<POSITION> Pos;
	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 });
		}
	}
}

line1)에서 보게 되면, #1에서 선언해놓은, 입력데이터들이 "순.서.대.로" 저장되어 있는 Vector를 통해 탐색을 진행한다.

line3)에서 보게 되면, 'POSITION'을 자료형으로 가지는 Vector를 하나 선언하게 된다.

그리고 line5 ~) 를 보게 되면 모든 좌표를 탐색하는 것을 확인할 수 있다.

모든 좌표를 하나하나 탐색을 하는 과정에서, 하나의 좌표 당 인접한 4칸을 탐색하면서(line13) 인접한 칸에 빈 칸이 몇 칸이 있는지(line 18), 그리고 인접한 칸에 "현재 학생이 좋아하는 친구가 몇 명이 있는지"(line21 ~ 29) 파악을 하고 있다.

그리고, 모든 정보가 다 파악되었다면, 최종적으로 Vector에 삽입을 하게 된다.

 

이렇게 Vector에 모든 좌표가 가지는 정보들을 저장했다면, 우리가 구하고자 하는 "최적의 자리"는 어떻게 구할 수 있을까 ??

이 Vector를 "조건에 맞게 정렬"을 시켜주면 될 것이다. 정렬을 시켜주면, Vector의 가장 앞쪽에 우리가 원하는 최적의 자리가 정렬되어서 배치되어 있을 것이고, 우리는 이 Vector의 가장 앞에 위치한 데이터를 현재 학생의 자리에 배치를 해주면 된다.

# 자리 배치를 위한 필요한 정보들을, 빈 칸으로 남아있는 모든 좌표에 대해서 구해서 Vector에 1차적으로 저장한다.
# 모든 좌표에 대한 탐색이 끝났다면, 이 Vector를 정렬시킴으로써 "최적의 자리"를 쉽게 구할 수 있다.

 

#4. 만족도 구하기

이제 어려운 과정은 모두 끝났다. #3에서 모든 학생들의 자리 배치가 끝났다면 이제 단순하게 만족도만 구하면 된다.

그런데 ! 이 과정에서 조금은 번거로운 과정이 하나 발생한다.

만족도를 구하기 위해서 모든 좌표를 탐색하면서, 해당 좌표에 있는 학생 번호를 가져온다고 가정해보자.

예를 들어서, (0 , 0)에 5번 학생이 배치되어 있을 때, 이 5번학생의 만족도를 구하기 위해서는 우리는 학생의 정보를 담아두었던, #1의 과정에서 선언해놓은 Vector를 모두 탐색해보면서 학생 번호가 '5'인 부분을 찾아서 계산을 해 주어야 한다.

물론 ! 이렇게 하더라도 절대 정답을 구하는데 있어서 큰 문제가 되지는 않는다.

그런데 너무 번거로운 과정인 것 같아서, 본인은 ! 이 과정을 위해서 #1에서 이 학생들의 정보를 '배열'로도 하나 더 선언해 주었다. 다시한번 가져오면 다음과 같은 형태로 선언해 주었다.

struct STUDENT
{
	int Num;
	int Friend[4];
};

STUDENT Student_Arr[MAX * MAX];
vector<STUDENT> Student;

여기서, Student_Arr[A] 에는 "A번 학생에 대한 정보" 가 저장될 것이다.

맵의 크기가 MAX 라고 가정한다면, 학생의 수는 최대 MAX * MAX 명이 될 것이고, 학생 번호 또한 MAX * MAX번이 나올 수가 있다. 따라서, 배열의 크기를 MAX * MAX로 선언해 주었다.

그럼 ! 이 과정을 Vector가 아닌 이 배열로 한번 구한다고 가정해보자.

(0 , 0)에 5번 학생이 배치되어 있을 때, 5번 학생의 만족도를 구하기 위해서는 ??

Student_Arr[5] 를 참조한다면, 이 5번학생이 좋아하는 친구들에 대한 정보를 바로바로 구할 수 있을 것이다.

이 과정을 위해서 #1에서 배열로도 하나 선언하고, Vector로도 하나 선언해 준 것이다.

 

그럼 ! 역으로, 처음부터 배열로만 선언해서 관리를 했으면 안될까? 에 대해서 생각을 해보자.

#3에서 유독 눈에 띄게 "순.서.대.로" 라는 말을 본인이 강조해 놓았다.

이렇게 배열로만 관리를 하게 된다면, #3의 과정인, 자리를 배치하는 과정을 "입력 데이터 순서대로" 배치를 하는데 또 다른 번거로움이 발생하게 된다.

물론 ! 배열에 멤버변수를 하나 더 추가해서 '입력된 순서'를 추가해서 자리를 배치 할 때 마다, 모든 배열을 탐색하면서 입력된 순서를 비교하면서 진행을 하더라도 문제는 없을 것이다.

하지만 ! 너무 번거롭기 때문에 본인은 그냥 "순서대로" 데이터를 관리하기 위한 Vector를 하나 선언해 주었고, 최종적으로 만족도를 구할 때 "학생의 정보를 바로 참조하기 위해"서 배열을 또 하나 선언해 주어서 관리해 주었다.

이 과정을 코드로 나타내면 다음과 같다.

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];
			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 <iostream>
#include <vector>
#include <algorithm>
 
#define MAX 25
using namespace std;
 
struct STUDENT
{
    int Num;
    int Friend[4];
};
 
struct POSITION
{
    int x;
    int 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)
    {
        if (A.Nearly_Friend == B.Nearly_Friend)
        {
            if (A.Nearly_Empty >= B.Nearly_Empty)
            {
                if (A.Nearly_Empty == B.Nearly_Empty)
                {
                    if (A.x <= B.x)
                    {
                        if (A.x == B.x)
                        {
                            if (A.y < B.y)
                            {
                                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;
        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];
            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);
        }
    }
}
 
void Solution()
{
    Set_Position();
    Calculate_Satisfy();
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}