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

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

21608번: 상어 초등학교

 

 

[ 문제풀이 ]

 

1. 맵의 모든 좌표를 돌면서 주변에 좋아하는 학생 수와 빈칸의 수를 체크하여 자리를 정합니다.

 

2. 좋아하는 학생 수가 같다면 빈 칸의 수가 많은 자리, 빈칸의 수까지 같다면 행의 번호가 낮은 칸, 마지막으로 행의 번호마저 같다면 열의 번호가 낮은 칸에 자리를 정해줍니다.

 

3. 2에서 좋아하는 학생 수도 0, 빈 칸의 수까지 0이라면 제일 처음 나오는 빈자리에 앉아야 하므로 최솟값을 0이 아닌 -1로 초기화해줍니다.

 

[ 소스코드 ]

 

#include<iostream>
#include<cmath>
 
using namespace std;
 
int N;
int arr[401][4];
int order[401];
int map[21][21];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int like(int y, int x, int cur)    //주변 좋아하는 학생 수 체크
{
    int cnt = 0;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy > 0 && yy <= N && xx > 0 && xx <= N) {
            for (int j = 0; j < 4; j++) {
                if (map[yy][xx] == arr[cur][j]) {
                    cnt++;
                }
            }
        }
    }
 
    return cnt;
}
 
int space(int y, int x)        //주변 빈 자리 수 체크
{
    int cnt = 0;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy > 0 && yy <= N && xx > 0 && xx <= N) {
            for (int j = 0; j < 4; j++) {
                if (map[yy][xx] == 0) {
                    cnt++;
                }
            }
        }
    }
 
    return cnt;
}
 
void seat(int cur)    //자리 정하기
{
    int y;
    int x;
    int spaceCnt = -1;    //0이 최솟값이므로 -1로 초기화
    int likeCnt = -1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (map[i][j] == 0) {    
                int tempLike = like(i, j, cur);
                int tempSpace = space(i, j);
                if (likeCnt < tempLike) {
                    likeCnt = tempLike;
                    spaceCnt = tempSpace;
                    y = i;
                    x = j;
                }
                else if (likeCnt == tempLike) {
                    if (spaceCnt < tempSpace) {
                        spaceCnt = tempSpace;
                        y = i;
                        x = j;
                    }
                }
            }
        }
    }
 
    map[y][x] = cur;
}
 
int ans()    //점수 구하기
{
    int ret = 0;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int cnt = like(i, j, map[i][j]);
            if (cnt > 0) {
                ret += pow(10, cnt - 1);
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N * N; i++) {
        int n;
        scanf("%d", &n);
        order[i] = n;
        for (int j = 0; j < 4; j++) {
            scanf("%d", &arr[n][j]);
        }
    }
 
    for (int i = 1; i <= N * N; i++) {
        seat(order[i]);
    }
 
    printf("%d", ans());
}