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

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

21608번: 상어 초등학교

 

 

구현문제입니다.

 

 

 

1. 단순구현으로 해결했다.

결론적으로 반복문을 통해서 각각의 학생들의 자리를 픽스시켜 주면 되기 때문에, 천천히 조건에 맞게 구현하면 된다.

 

2. 3가지 조건중 1번, 2번을 통해서 각각의 학생별로 해당하는 위치를 도출했다. 3번은 우선순위에 의해서 일반적인 반복문을 사용하면 자동으로 결정됨.

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

그런데 왠 런타임 에러??

 

주의점은 만약 좋아하는 친구와, 빈칸 모두 없는 상황일때는 3번 조건에 의해서 가장 가까운 칸을 선택하도록 예외처리를 추가해주어야 한다. (본 코드 storePosition 함수 아래쪽 참고)

 

 

 

정답 코드

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

vector <int> friends[401];
vector <int> vec; // 순서저장
int arr[25][25] = { 0, }; // 위치가 픽스 되면
int n = 0;
int result = 0;

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void storePosition(int& y, int& x, int v) {


	int rf = 0;
	int rb = 0;
	int ry = 0;
	int rx = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != 0)
				continue;

			int cy = i;
			int cx = j;
			int fav = 0;
			int bla = 0;


			for (int k = 0; k < 4; k++) {
				int ny = cy + y_ar[k];
				int nx = cx + x_ar[k];

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

				for (int u = 0; u < 4; u++) {
					if (arr[ny][nx] == friends[v][u])
						fav++;
					else if(arr[ny][nx] == 0)
						bla++;
				}
			}

			if (fav > rf) {
				rf = fav;
				rb = bla;
				ry = cy;
				rx = cx;
			}
			else if (fav == rf) {
				if (bla > rb) {
					rb = bla;
					ry = cy;
					rx = cx;
				}
			}

		}
	}



	if (ry == 0 && rx == 0) { // 중요
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (arr[i][j] == 0) {
					ry = i, rx = j;
					break;
				}
			}
			if (ry != 0 && rx != 0)
				break;
		}

	}

	y = ry, x = rx;

}

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

	cin >> n;

	for (int i = 0; i < n*n; i++) {
		int temp;
		int temp2[4];

		cin >> temp;
		vec.push_back(temp);

		for (int j = 0; j < 4; j++) {
			cin >> temp2[j];
			friends[temp].push_back(temp2[j]);
		}
	}


	for (int i = 0; i < n*n; i++) {
		int v = vec[i];
		int y = 0; int x = 0;
		storePosition(y, x, v);
		arr[y][x] = v;



	}


	// 점수 계산 

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {

			int cy = i;
			int cx = j;
			int cnt = 0;

			for (int k = 0; k < 4; k++) {
				int ny = cy + y_ar[k];
				int nx = cx + x_ar[k];

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

				for (int u = 0; u < 4; u++) {
					if (arr[ny][nx] == friends[arr[cy][cx]][u])
						cnt++;
				}

			}

			if (cnt == 1)
				result += 1;
			else if (cnt == 2)
				result += 10;
			else if (cnt == 3)
				result += 100;
			else if (cnt == 4)
				result += 1000;
		}
	}

	cout << result << endl;


	return 0;
}