[BOJ 백준] 21608번 상어 초등학교

문제

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

21608번: 상어 초등학교

접근

 문제에서 주어진 조건은 아래와 같다.

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

 입력받은 학생의 순서대로 위의 조건에 맞게 알맞은 자리에 배정해주면 되는 문제이다. 나는 학생을 입력받을 때마다 교실의 빈자리를 모두 확인하면서 임의의 자리 n에 대하여 n의 인접한 자리(상,하,좌,우)의 친구의 수와 빈자리의 수를 count하여 조건에서 요구하는 대로 인접한 자리에 친구가 많고, 만약 친구의 수가 같다면 주변에 빈자리가 많은 순으로 값을 갱신해 주었다. 따라서 이렇게 모든 자리를 방문한 후에는 가장 알맞은 자리를 구할 수 있게 되고, 그 자리에 학생을 앉히면 된다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k, st[405][5], ans[25][25] = {0}, dx[]  = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
    cin >> n;
    for (int num = 0; num < n * n; num++) {
        cin >> k;
        cin >> st[k][0] >> st[k][1] >> st[k][2] >> st[k][3];
        pair <int, int> p, point; // 인접한 칸 중 좋아하는 학생 수, 인접한 칸 중 빈칸의 수
        p.first = -1;
        p.second = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (ans[i][j] != 0)
                    continue;
                int friend_counter = 0, empty_counter = 0;
                for (int l = 0; l < 4; l++) {
                    int newx = i + dx[l];
                    int newy = j + dy[l];
                    if (newx < 0 || newy < 0 || newx >= n || newy >= n)
                        continue;
                    if (ans[newx][newy] == 0)
                        empty_counter++;
                    else if (ans[newx][newy] == st[k][0])
                        friend_counter++;
                    else if (ans[newx][newy] == st[k][1])
                        friend_counter++;
                    else if (ans[newx][newy] == st[k][2])
                        friend_counter++;
                    else if (ans[newx][newy] == st[k][3])
                        friend_counter++;
                }
                if (friend_counter > p.first) {
                    p.first = friend_counter;
                    p.second = empty_counter;
                    point.first = i;
                    point.second = j;
                } else if (friend_counter == p.first && empty_counter > p.second) {
                    p.first = friend_counter;
                    p.second = empty_counter;
                    point.first = i;
                    point.second = j;
                }
            }
        }
        ans[point.first][point.second] = k;
    }
    int ans_num = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int add = 0;
            for (int k = 0; k < 4; k++) {
                int newx = i + dx[k];
                int newy = j + dy[k];
                if (newx < 0 || newy < 0 || newx >= n || newy >= n)
                    continue;
                for (int l = 0; l < 4; l++) {
                    if (st[ans[i][j]][l] == ans[newx][newy])
                        add++;
                }
            }
            if (add == 1) 
                ans_num += 1;
            else if (add == 2) 
                ans_num += 10;
            else if (add == 3)
                ans_num += 100;
            else if (add == 4)
                ans_num += 1000;
        }
    }
    cout << ans_num;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study