[백준 21680] 상어 초등학교

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

21608번: 상어 초등학교

#include <cstdio>
int N;
int board[20 + 2][20 + 2];

struct _st
{
	int n;
	int a, b, c, d;
	int x, y;
}S[400 + 2];

static int dir_x[4] = { 0, 0, 1, -1 };
static int dir_y[4] = { 1, -1, 0, 0 };

int value[5] = { 0, 1, 10, 100, 1000 };

void debug()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%d ", board[i][j]);
		}
		printf("\n");
	}
}

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N * N; i++) {
		int n = 0, a = 0, b = 0, c = 0, d = 0;
		scanf("%d %d %d %d %d", &n, &a, &b, &c, &d);
		S[i] = { n, a, b, c, d };
	}
}

void get_loc()
{
	for (int s = 0; s < N * N; s++) {
		int max_blank = 0;
		int max_bff = 0;
		int opt_row = 0x7fffffff; 
		int opt_col = 0x7fffffff;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] != 0) continue;
				
				int blank = 0;
				int bff = 0;
				for (int p = 0; p < 4; p++) {
					int nx = i + dir_x[p];
					int ny = j + dir_y[p];
					if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
					if (board[nx][ny] == 0) blank++;
					if (board[nx][ny] == S[s].a || board[nx][ny] == S[s].b || board[nx][ny] == S[s].c || board[nx][ny] == S[s].d) bff++;
				}
				if ((max_bff < bff) ||
					(max_bff == bff && max_blank < blank) ||
					(max_bff == bff && max_blank == blank && opt_row > i) ||
					(max_bff == bff && max_blank == blank && opt_row == i && opt_col > j)) {
					max_bff = bff;
					max_blank = blank;
					opt_row = i;
					opt_col = j;
				}
			}
		}
		board[opt_row][opt_col] = S[s].n;
		S[s].x = opt_row;
		S[s].y = opt_col;
	}

}


int is_good()
{
	int score = 0;
	for (int s = 0; s < N * N; s++) {
		int x = S[s].x;
		int y = S[s].y;
		int bff = 0;
		for (int p = 0; p < 4; p++) {
			int nx = x + dir_x[p];
			int ny = y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (board[nx][ny] == S[s].a || board[nx][ny] == S[s].b || board[nx][ny] == S[s].c || board[nx][ny] == S[s].d) bff++;
		}
		score += value[bff];
	}
	return score;
}


int main()
{
	input();
	get_loc();
	int ans = is_good();
	printf("%d\n", ans);
	return 0;
}

선호하는 친구를 이전에 풀었던 것 처럼 룩업테이블 만들었으면 좀 더 깔끔했을듯

 

---

나의 이전풀이...는 다음과 같다. 

맞왜틀 아님... 생각 좀 해라

#include <cstdio>
int N, M;	// N * N, 학생수 
int board[20 + 5][20 + 5];

struct _st
{
	int stnum;
	int x = 0x7fffffff;
	int y = 0x7fffffff;
};

_st student[400 + 5];
int prefer, blank;	// 각 탐색에서 쓸 변수 

int lookup[400 + 5][4 + 5];	// 선호하는 친구 룩업테이블 
int score[5] = { 0, 1, 10, 100, 1000 };	// 점수판

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void input()
{
	scanf("%d", &N);
	M = N * N;	// 학생수
	for (int i = 1; i <= M; i++) {
		int s = 0;
		scanf("%d", &s);
		student[i].stnum = s;
		for (int j = 0; j < 4; j++) {
			scanf("%d", &lookup[s][j]);
		}
	}
}


void chk(int stnum, int x, int y)
{
	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
		if (board[nx][ny] == 0) blank++;	// 빈칸 확인 
		for (int k = 0; k < 4; k++) {
			if (board[nx][ny] != 0 && board[nx][ny] == lookup[stnum][k]) prefer++;	// 좋아하는 학생 확인 
		}
	}
	//printf("pf : %d bk : %d\n", prefer, blank);
}




void simul()
{
	for (int s = 1; s <= M; s++) {
		int max_prefer = 0;	
		int max_blank = 0;

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (board[i][j]) continue;	// 해당 자리에 이미 누가 앉았다면 다음 자리를 탐색
				prefer = 0;	// 초기화
				blank = 0;

				chk(student[s].stnum, i, j);

				if (max_prefer < prefer) {
					max_prefer = prefer;
					max_blank = blank;		// blank도 같이 갱신 필요하다. 
					student[s].x = i;
					student[s].y = j;
				}
				if (max_prefer == prefer) {
					if (max_blank < blank) {
						max_blank = blank;
						student[s].x = i;
						student[s].y = j;
					}
				}
				if (max_prefer == prefer && max_blank == blank) {
					if (i < student[s].x) {
						student[s].x = i;
						student[s].y = j;
					}
				}
				if (max_prefer == prefer && max_blank == blank && i == student[s].x) {
					if (j < student[s].y) {
						student[s].x = i;
						student[s].y = j;
					}
				}
				//printf("[%d] %d %d\n", student[s].stnum, student[s].x, student[s].y);
			}
		}
		board[student[s].x][student[s].y] = student[s].stnum;
	}
	//debug();
}


int output()
{
	int total = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int cnt = 0;
			for (int p = 0; p < 4; p++) {
				int ni = i + dir_x[p];
				int nj = j + dir_y[p];

				if (ni < 1 || ni > N || nj < 1 || nj > N) continue;
				for (int k = 0; k < 4; k++) {
					if (board[ni][nj] == lookup[board[i][j]][k]) cnt++;
				}
			}
			total += score[cnt];
		}
	}
	return total;
}


int main()
{
	input();
	simul();
	int ans = output();
	printf("%d\n", ans);
	return 0;
}

나는 가장 생각하기 쉬운 방법으로 코드를 짰다. 

그냥 우선순위대로 1번 많으면 => 2번 많으면 => 3번... 

여기서 내가 했던 실수는 변수가 어떤일을 하는지 생각하지 않고 무지성으로 (진짜 무지성으로 짠듯.. ) 코드를 짠 것이다. 

 

맵을 스캔하면서 만약 해당 자리에서 선호하는 학생 수가 가장 많으면 max_prefer를 prefer로 갱신하고, 이때 max_blank도 blank로 갱신해야 한다. 왜냐하면 해당 자리가 학생이 앉을 후보가 된 것이기 때문이다. 애먼 좌석에서 인접한 빈칸의 개수를 구하면 안되고, 후보인 좌석에서 "인접한 선호하는 학생 수"와 "인접한 빈칸의 개수"를 담아주어야 한다.