[백준 / C++] 21608번: 상어 초등학교 (삼성 SW 역량 테스트 기출)

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

21608번: 상어 초등학교

 

난이도: solved.ac 골드 5

 

구현 방법

문제에서 주어진 세 가지 조건 그대로 구현하면 되는 문제다.

 

먼저 첫 번째 조건을 살펴보자.

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

 

이를 구현하기 위해 학생들을 배치할 공간 board[N][N]을 만들고, board가 0인 모든 빈자리를 기준으로 인접한 상하좌우 캉을 탐색해 좋아하는 학생이 몇 명 있는지 파악한다.

 

그리고 두 번째 조건

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

 

각 칸들의 인접한 칸 중 비어있는 칸이 몇 개인지 빠르게 파악하기 위해 emptys라는 2차원 배열을 만들어 각 칸에 인접한 칸 중 빈 칸이 몇 개인지 적어주었다.

 

따라서 새로 탐색한 칸의 인접한 자리에 앉은 좋아하는 학생의 수가 이전에 탐색한 칸들 중 인접한 칸에 앉은 좋아하는 학생의 수의 최대값과 같다면 인접한 빈 칸의 개수를 비교해 새로 탐색한 칸의 인접한 빈 칸이 더 많다면 현재 찾고 있는 앉힐 자리를 새로 갱신해주었다.

 

그리고 세 번째 조건

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

 

이 조건은 그냥 탐색할 때 맨 왼쪽 위 자리부터 탐색하면 자연스럽게 만족하게 된다.

 

따라서 세 번째 조건은 없는 셈치고 구현했다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int N;
int board[20][20], emptys[20][20], prefer[401][4];
int dy[4] = { 1,0,-1,0 }, dx[4] = { 0,1,0,-1 };
// board: 배정할 자리
// emptys: 비어있는 칸의 개수 (empty seats)
// prefer: 각 학생들의 선호 번호 저장
void emptys_init();
void find_seat(int student);
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	emptys_init();
	int student, i, j, k;
	for (i = 0; i < N * N; i++) {
		cin >> student;
		for (j = 0; j < 4; j++) {
			cin >> prefer[student][j];
		}
		find_seat(student);
	}
	int ans = 0;
	// 각 자리별로 해당 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 파악해 만족도 조사
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			int cnt = 0;	// 인접한 칸에 앉은 학생 중 좋아하는 학생의 수
			for (int dir = 0; dir < 4; dir++) {
				int ny = i + dy[dir];
				int nx = j + dx[dir];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N)
					continue;
				for (k = 0; k < 4; k++) {
					if (board[ny][nx] == prefer[board[i][j]][k]) {
						cnt++;
						break;
					}
				}
			}
			if (cnt == 1)
				ans++;
			else if (cnt == 2)
				ans += 10;
			else if (cnt == 3)
				ans += 100;
			else if (cnt == 4)
				ans += 1000;
		}
	}
	cout << ans;
}
 
void emptys_init() {
	// 꼭지점
	emptys[0][0] = 2;
	emptys[0][N - 1] = 2;
	emptys[N - 1][0] = 2;
	emptys[N - 1][N - 1] = 2;
	for (int i = 1; i < N - 1; i++) {
		emptys[0][i] = 3;	// 위쪽 모서리
		emptys[N - 1][i] = 3;	// 아래쪽 모서리
		emptys[i][0] = 3;	// 왼쪽 모서리
		emptys[i][N - 1] = 3;	// 오른쪽 모서리
		for (int j = 1; j < N - 1; j++)
			emptys[i][j] = 4;	// 안쪽
	}
}
 
void find_seat(int student) {
	int i, j, k, max = -1;	// 인접한 자리에 있는 좋아하는 학생의 수 최댓값
	int y, x, emptyseat;
	// y, x : 배치할 자리의 후보 좌표
	// emptyseat: 후보 좌표에서 인접한 자리 중 비어있는 곳의 개수
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			// 이미 자리가 있는 경우는 pass
			if (board[i][j])
				continue;
			int cnt = 0;	// 인접한 자리에 좋아하는 학생이 몇 명이 있는지
			for (int dir = 0; dir < 4; dir++) {
				int ny = i + dy[dir];
				int nx = j + dx[dir];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N)
					continue;
				for (k = 0; k < 4; k++) {
					if (board[ny][nx] == prefer[student][k]) {
						cnt++;
						break;
					}
				}
			}
			if (cnt > max) {
				// 현재의 자리에서 인접한 자리에 좋아하는 학생의 수가 더 많을 때
				max = cnt;
				// 후보 자리 새로 갱신
				y = i;
				x = j;
				emptyseat = emptys[y][x];
			}
			else if (cnt == max) {
				// 인접한 자리에 있는 좋아하는 학생의 수가 기존 후보 자리와 같은 경우
				// 인접한 자리 중 비어있는 자리가 더 많을 때 후보 새로 갱신
				if (emptys[i][j] > emptyseat) {
					y = i;
					x = j;
					emptyseat = emptys[y][x];
				}
			}
		}
	}
	board[y][x] = student;	// 자리 확정
	// 인접한 칸들 emptys 하나씩 감소시키기
	for (i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= N || nx < 0 || nx >= N)
			continue;
		emptys[ny][nx]--;
	}
}

 

성능

코드 제출 결과