[BOJ/C++] 21608(상어 초등학교)

1. Link

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

2. 풀이 과정

1. 설명을 읽다보면 특별한 알고리즘을 쓰지 않은 구현임을 바로 알 수 있습니다. - 구현

2중 for문을 돌며 다음과 같은 순서로 진행이 됩니다.

1. 임의의 빈 칸 (x, y) 기준 좋아하는 학생이 가장 많이 인접한 칸으로 자리를 설정합니다.

2. 1을 만족하는 경우가 여럿이라면, 인접 칸 중에 빈 칸이 가장 많은 자리를 설정합니다.

3. 2까지 만족하는 경우가 여럿이면, 행 번호가 가장 작은, 행 번호까지 같다면 열 번호가 가장 작은 자리를 설정합니다.

• 참고로 2중 for문으로 풀다보면 3번 조건은 자동으로 생략이 된다는 것을 알 수 있습니다. x, y가 1부터 n까지로 진행되므로 행 번호는 기존의 값이 같거나 작을 것이고, 열 번호 또한 기존의 값이 더 작을 것이기 때문입니다.

• setting 메서드를 사용해 값을 대입할 위치, 해당 위치의 선호하는 사람 및 빈 칸 인접 정도를 업데이트합니다.

• test 메서드를 사용해 조건에 맞는 위치를 확인합니다. 만약 업데이트할 사항이 생기면 setting 메서드를 호출하여 값을 입력할 위치와 관련된 정보를 업데이트합니다.

3. 함수 설명

void test(int x, int y, int num): x,y 위치에서 상하좌우를 탐색하고 인접한 칸과 빈 칸의 개수를 탐색, 탐색 후 변경점 발생 시 대입할 번호에 대한 값 재지정

void setting(int x, int y, int adjCnt, int emptyCnt): x,y 위치에서 값을 재지정
pair<int, int> cur에 x,y라는 조건에 맞는 지정해줄 위치를 대입하고 curClose, curEmpty에 adjCnt, emptyCnt를 대입하여 해당 상태에서의 최적값을 대입

4. 정답 코드

#include<iostream>
#define p pair<int, int>
using namespace std;

int n, answer = 0;
int a[21][21];
int dx[]{ 0,1,0,-1 };
int dy[]{ 1,0,-1,0 };
bool like[401][401]{ 0 };
int q[401];
p cur;
int curClose, curEmpty;//인접 cnt, 빈 cnt

void setting(int x, int y, int adjCnt, int emptyCnt) {
	cur = { x,y };
	curClose = adjCnt;
	curEmpty = emptyCnt;
}

void test(int x, int y, int num) {
	int adj = 0, emptyLoc = 0;
	for (int i = 0; i < 4; ++i) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
		if (like[num][a[nx][ny]]) ++adj;
		else if (a[nx][ny] == 0) ++emptyLoc;
	}
	if (adj > curClose) setting(x, y, adj, emptyLoc);	
	else if(adj == curClose) {
		if(emptyLoc > curEmpty) setting(x, y, adj, emptyLoc);
		//왼쪽 위에서 오른쪽 아래로 진행되므로 행의 번호 및 열의 번호는 자동으로 이전이 더 작을 수 밖에 없음
	}
}

void input() {
	cin >> n;
	int l;
	for (int i = 0; i < n * n; ++i) {
		cin >> q[i];
		for (int j = 0; j < 4; ++j) {
			cin >> l;
			like[q[i]][l] = true;
		}
	}
}

void solution() {
	input();
	for (int x = 0; x < n * n; ++x) {
		cur = { 0,0 };
		curClose = curEmpty = -1;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (a[i][j] != 0) continue;
				test(i, j, q[x]);
			}
		}
		a[cur.first][cur.second] = q[x];
	}
	//after work done
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			int cnt = 0, add = 1;
			for (int dir = 0; dir < 4; ++dir) {
				int nx = i + dx[dir];
				int ny = j + dy[dir];
				if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
				if (like[a[i][j]][a[nx][ny]]) ++cnt;
			}
			if (cnt == 0) continue;
			else {
				while (--cnt) {
					add *= 10;
				}
				answer += add;
			}
		}
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}