[백준][C++] 21608 상어 초등학교

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

21608번: 상어 초등학교

 

[백준][C++] 21608 상어 초등학교

 

Out of bounds 런타임에러가 나와서 배열 크기때문인가? 했는데 예외 케이스 처리가 안되었다.

 

내가 세운 학생의 자리를 찾는 알고리즘

 

행이 가장 작은 칸, 열이 가장 작은 칸 순으로 순회

1. 인접한 좋아하는 학생 수가 이전에 저장한 값(like)보다 크면 해당 인덱스 저장

2. 인접한 좋아하는 학생 수가 이전에 저장한 값(like)과 같으면 비어있는 칸 갯수가 이전에 저장한 값(empty)보다 클 때 인덱스 저장

 

이렇게 짜면 아래 테케의 예외를 못잡아준다.

2. 에서 empty값이 0이기 때문에 9는 자리가 안정해진다..

// Input
3
1 2 3 4 5
2 1 3 4 5
3 1 2 4 5
4 1 2 3 5
5 1 2 3 4
6 1 2 3 4
7 1 2 3 4
8 1 2 3 4
9 1 2 3 4

// 자리 배치
4 2 7
3 1 5
8 6 9

// Output
134

 

(테스트케이스 출처: https://jamluck.tistory.com/5)

 

 

find()의 empty=-1 로 초기화 해줬다.

 

#include <iostream>
using namespace std;

int N;
int student;
int arr[401][4];
int map[20][20] = {};
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int countLike(int y, int x, int s) {
	int ret = 0;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

		for (int j = 0; j < 4; j++) {
			if (map[ny][nx] == arr[s][j]) {
				ret++;
				break;
			}
		}
	}

	return ret;
}

int countEmpty(int y, int x) {
	int ret = 0;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (map[ny][nx] == 0) ret++;
	}

	return ret;
}

void find(int s) {
	int like = 0;
	int empty = -1;
	int fi;
	int fj;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j]) continue;

			int cl = countLike(i, j, s);
			int ce = countEmpty(i, j);
			if (like < cl) {
				like = cl;
				empty = ce;
				fi = i;
				fj = j;
			}
			else if (like == cl) {
				if (empty < ce) {
					empty = ce;
					fi = i;
					fj = j;
				}
			}
		}
	}

	map[fi][fj] = s;
}

int calculate() {
	int ret = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int s = map[i][j];
			int cnt = 0;
			for (int k = 0; k < 4; k++) {
				int ny = i + dy[k];
				int nx = j + dx[k];

				if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
								
				for (int l = 0; l < 4; l++) {
					if (map[ny][nx] == arr[s][l]) {
						cnt++;
						break;
					}
				}
			}
			if (cnt == 2) ret += 10;
			else if (cnt == 3) ret += 100;
			else if (cnt == 4)ret += 1000;
			else ret += cnt;
		}
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	student = N * N;

	int s;
	for (int i = 1; i <= student; i++) {
		cin >> s;

		for (int j = 0; j < 4; j++) {
			cin >> arr[s][j];

		}
		find(s);
	}

	cout << calculate();

	return 0;
}