boj, 백준) 21608. 상어 초등학교 (C/C++)

1. 문제 링크

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

21608번: 상어 초등학교

2. 문제 개요

교실이 하나 있다. 교실은 N x N크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N^2명이다.  학생은 1번부터 N^2번까지 번호가 매겨져 있고 (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.

 

|r_1 - r_2 | + |c_1 - c_2| = 1을 만족하면 두 칸은 인접하다고 함.

 

다음과 같은 조건을 만족해야한다.

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

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

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

 

인접한 칸에 좋아하는 학생수에 따른 점수가 주어질 때, 학생들의 만족도의 총합을 구해보자.

 

3. 문제 힌트

인접하다는 의미를 생각해보면, 상 하 좌 우 바로 붙어있는 칸을 의미한다.

 

조건에 맞춰 구현만 하면 되는 문제이다. 조건을 잘 살펴보자

 

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

--> 이를 구현하기 위해서는 '비어있는 칸' 중에서 '좋아하는 학생'이 몇 명 있는지 매번 세어야 한다. 이를 기록하는 어떤 변수를 하나 선언하자.

 

-위의 조건을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.

--> 이것도 '인접한 칸'중에서 '비어있는 칸'이 몇 개 있는지 세어야 한다. 이를 기록하는 어떤 변수를 하나 선언하자.

 

-세 번째 조건을 해석해보면 결국 우선순위는 왼쪽 위이다. 어떤 순서로 순회하면 추가 연산 없이 바로 알 수 있을까?

 

4. 문제 풀이

3번란에도 적었던 것처럼,  조건에 맞춰서 구현만 하면 된다.

 

(1) 번 조건을 만족하지 않으면, (2) 번 조건을 만족하지 않으면, 3번 조건을... 이런 식으로 진행된다.

 

한 번의 N^2 탐색으로 한 학생을 결정지어주도록 구현했다.

그래서 먼저 세 번째 조건을 살펴보자, 

뜻을 살펴보면 결국 왼쪽 위가 가장 우선순위가 높다. 이때는, 1,2번 조건을 모두 만족해야한다. 즉, 학생이 인접한 칸이 동일하고 인접한 칸중 비어있는 칸이 동일하다는 것. 이럴 경우, 오른쪽 밑에서부터 왼쪽위 방향으로 순회를 하고, 값이 같을 때는 덮어씌워(갱신) 주는 것으로 3번 조건은 해결할 수 있다.

 

1번 조건을 보자,

1번 조건에서 인접한 칸이 여러 개 존재할 수 있다. 그래서 Vector 변수를 선언해서 비어있는 칸의 개수가 같다면 push_back을 해서 뒤에 삽입해 주었다. 그런데 여기서, 지금 Vector에 존재하는 인접한 칸에 존재하는 좋아하는 학생의 수보다 큰 자리를 발견한다면 Vector를 Clear 해주고 새로운 수를 삽입해 주었다.

 

다음은 마지막으로 2번 조건,

1번 조건에서 인접한 칸에 친한 친구가 몇 명인지 셀 때 빈칸의 개수도 함께 센다. 친한 친구 값이 현재 삽입된 Vector의 개수와 동일할 때, 즉, push_back 될 때, 빈칸 개수의 최댓값을 갱신해주자(크거나 같은 경우에만), 왜냐하면 3번 조건을 만족하기 위해서이다. 오른쪽아래에서 왼쪽위로 순회하도록 했기 때문에, 같을 경우에는 갱신을 해주어야 3번조건을 자동으로 만족시킬 수 있다.

 

5. 코드

#include <cstdio>
#include <vector>
using namespace std;

struct COORD {
	COORD() {}
	COORD(int y_, int x_) :y(y_), x(x_) {}
	int y, x;
};

int n, ans;
vector<vector<int>> prefer;
vector<int> order;
int map[21][21];

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

int main()
{
	scanf("%d", &n);
	prefer.resize(n*n + 1);

	for (int i = 0; i < n*n; ++i) {
		int who;
		scanf("%d", &who);
		order.push_back(who);

		for (int j = 0; j < 4; ++j) {
			int item;
			scanf("%d", &item);
			prefer[who].push_back(item);
		}
	}

	for (int cur : order) {
		int candi_friend_num = 0;
		int candi_blank_num = 0;
		vector<pair<COORD, int>> candi;
		pair<COORD, int> candi_blank;

		for (int cy = n; cy >= 1; --cy) {
			for (int cx = n; cx >= 1; --cx) {
				if (map[cy][cx] != 0)
					continue;

				int adj_blank_num = 0;
				int adj_friend_num = 0;

				for (int dir = 0; dir < 4; ++dir)
				{
					int ny = cy + dy[dir];
					int nx = cx + dx[dir];

					if (ny <1 || nx <1 || ny>n || nx >n)
						continue;

					if (map[ny][nx] == 0) {
						++adj_blank_num;
					}
					else
					{
						for (int item : prefer[cur]) {
							if (item == map[ny][nx])
								++adj_friend_num;
						}
					}
				}

				if (adj_friend_num > candi_friend_num) {
					candi.clear();
					candi.push_back({ COORD(cy, cx), adj_friend_num });
					candi_friend_num = adj_friend_num;
					candi_blank = { COORD(cy, cx), adj_blank_num };
					candi_blank_num = adj_blank_num;
				}
				else if (adj_friend_num == candi_friend_num)
				{
					if (adj_blank_num >= candi_blank_num) {
						candi.push_back({ COORD(cy, cx), adj_friend_num });
						candi_blank = { COORD(cy, cx), adj_blank_num };
						candi_blank_num = adj_blank_num;
					}
				}
			}
		}

		if (candi.size() == 1)
			map[candi[0].first.y][candi[0].first.x] = cur;
		else
			map[candi_blank.first.y][candi_blank.first.x] = cur;
	}

	for (int cy = 1; cy <= n; ++cy) {
		for (int cx = 1; cx <= n; ++cx) {

			int num = 0;
			for (int dir = 0; dir < 4; ++dir) {
				int nx = cx + dx[dir];
				int ny = cy + dy[dir];

				if (ny <1 || nx <1 || ny>n || nx >n)
					continue;

				for (int item : prefer[map[cy][cx]]) {
					if (item == map[ny][nx])
						++num;
				}

			}
			if (num == 1)
				ans += 1;
			else if (num == 2)
				ans += 10;
			else if (num == 3)
				ans += 100;
			else if (num == 4)
				ans += 1000;
		}
	}

	printf("%d\n", ans);

	return 0;
}

6. 결과