BOJ 21608, 상어 초등학교

Source: BOJ 21608 상어 초등학교

상어 초등학교

문제를 요약해 보자면 N X N격자판에 본인이 좋아하는 학생이 인접한 칸에 얼마나 있는지 파악하는 문제이다.

문제의 조건은 다음과 같다

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다

2. 1을 만족하는 칸이 여러개이면, 인접한 칸 중에서 비어있는 칸이 가장 ㅁ낳은 칸으로 자리를 정한다

3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다

문제의 조건 1, 2, 3을 각각 POINT로 각각의 점수를 할당하고 만족하면 그 칸에 대한 점수를 부여하는 방식으로 칸을 선택하도록 로직을 짰다

PS Logic

1. STUDENT라는 구조체를 만든 후 자신의 번호, 좋아하는 학생의 번호들, 칸의 row/col을 멤버 변수로 만든다

2. STUDENT 구조체의 배열 st[400]을 만들고 입력으로 주어진 학생의 번호와 좋아하는 학생을 저장한다

3. getPoint()라는 함수를 만들고 인접한 칸에 좋아하는 학생이 있으면 +10, 인접한 칸이 빈칸이면 +1을 하는 방식으로 구현한다

4. getPoint()함수에서 가장 point가 큰 칸에 대해 현재 학생을 넣는다

5. 학생의 수만큼 반복한 후 문제를 해결한다

#include <bits/stdc++.h>
using namespace std;
#define MAX 20
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int n;
int board[MAX][MAX];
struct STUDENT
{
    int me;
    int fri[4];
    int row, col;
};
STUDENT st[400];

int getPoint(int x, int y, int s)
{
    int point = 0;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n)
            continue;
        if (board[nx][ny] == 0)
            point++;
        else
        {
            for (int j = 0; j < 4; j++)
            {
                if (board[nx][ny] == st[s].fri[j])
                    point += 10;
            }
        }
    }
    return point;
}

void setStudent(int px, int py, int i)
{
    board[px][py] = st[i].me;
    st[i].row = px;
    st[i].col = py;
}

int calcPoint(int s)
{
    int point = 0;
    int x = st[s].row;
    int y = st[s].col;
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n)
            continue;
        for (int f = 0; f < 4; f++)
        {
            if (board[nx][ny] == st[s].fri[f])
            {
                if (point == 0)
                    point++;
                else
                {
                    point *= 10;
                }
            }
        }
    }

    return point;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n * n; i++)
    {
        cin >> st[i].me >> st[i].fri[0] >> st[i].fri[1] >> st[i].fri[2] >> st[i].fri[3];
    }
    for (int i = 0; i < n * n; i++)
    {
        int px = -1;
        int py = -1;
        int point = -1;
        for (int x = 0; x < n; x++)
        {
            for (int y = 0; y < n; y++)
            {
                if (board[x][y] == 0)
                {
                    int curPoint = getPoint(x, y, i);
                    if (point < curPoint)
                    {
                        px = x;
                        py = y;
                        point = curPoint;
                    }
                }
            }
        }
        setStudent(px, py, i);
    }

    int ret = 0;
    for (int i = 0; i < n * n; i++)
    {
        ret += calcPoint(i);
    }
    cout << ret;
    return 0;
}