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

21608번: 상어 초등학교

 

삼성 SW 역량 테스트 기출 문제

에 수록된 문제. 

실버1 문제이고 나온지 얼마 안 돼보이는 문제였다.

문제가 과하게 친절하게 해야할 것들을 다 알려준다.

문제에 나온대로만 구현해주면 풀 수 있다.

(물론 나는 학생 수를 잘못 고려해서 틀렸다. 아마 대부분 사람들이 이것때문에 런타임 에러나서 틀린 것 같았다. 학생 수가 N * N명인데, N으로만 생각해서 틀렸다. 좀 더 생각했으면 좋았을 것 같은데, 게시판에 누가 이렇게 올려놓은 걸 보고 바로 알 수 있었다.)

 

문제풀이

문제에 심각하게 친절하게 나와있어서 따로 정리할 필요도 없다.

학생의 자리를 순서대로 정해줘야 하는데, 우선순위는 다음과 같다.

1. 자리 주변에 자기가 좋아하는 사람이 많은 순
2. 1이 여러개라면 주변에 빈 칸이 많은 순
3. 그리고 2도 여러개라면, 행이 낮은 순, 그마저도 여러개라면 열이 낮은 순

으로 우선순위를 정해서 자리를 정해주기만 하면 된다.

 

나는 이 문제를 보고 (1, 1) ~ (N, N)까지 순차적으로 탐색하면 3번의 조건은 자동으로 충족을 시킬 수 있게되고,

자리 주변에 자기가 좋아하는 사람이 더 많은지? 같다면 주변에 빈 칸이 몇개인지? 를 비교해줘서

문제의 조건에 맞는 자리의 좌표를 저장해두고 해당 좌표에 학생의 번호를 붙이는 식으로 구현했다.

 

또한 문제의 조건에 |r1 - r2| + |c1 + c2| = 1이 인접한 곳이라 했는데, 이 조건은 상, 하, 좌, 우만 인접하다는 뜻이다.

 

시간복잡도를 최악으로 계산해 봤을 때

학생의 수 : 20 * 20

칸의 수 : 20 * 20

특정 학생이 좋아하는 학생의 수 : 4

상, 하, 좌, 우 고려하는 경우 : 4

이므로,

400 * 400 * 4 * 4 = 2,560,000이 된다.

 

시간제한이 1초(약 100,000,000번의 연산)이므로 시간이 널널한 편에 속한다.

 

코드를 살펴보자.

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

// |r1 - r2| + |c1 - c2| = 1이 인접한 것. ->행이 1차이나거나 열이 1차이나는 경우 즉, 상, 하, 좌, 우

int studentCnt;
int classRoom[21][21];
int nearLeft[21][21];
vector<int> studentVec;
vector<int> studentLove[401]; // 틀린이유 : 학생 수는 최대 21명이 아니라 401명이다.
pair<int, int> direction[4] = {
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1}
};
int addLove[5] = { 0, 1, 10, 100, 1000 };
int ans;

사용한 STL과 변수

• studentCnt : 입력받는 N, 학생 수
• classRoom 배열 : 각 칸에 어떤 학생의 번호가 앉아있는지 저장하는 배열
• nearLeft 배열 : 해당 칸이 주변에 몇 칸이 비어있는지 저장하는 배열
• studentVec 벡터: 자리를 정하는 학생의 번호 순서를 기록해두는 벡터
• studentLove 벡터 : 특정 학생이 좋아하는 4명의 학생의 번호를 각각 기록하는 벡터
• direction 배열 : 상, 하, 좌, 우 순서대로 탐색할 수 있도록 현재 칸의 좌표에서 더해주기만 하면 되도록 만든 배열.
• addLove 배열 : 각 칸의 주변에 좋아하는 학생이 몇 명인지에 따라 바로 더해줄 수 있도록 만들어놓은 배열
• ans : 출력값

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

	cin >> studentCnt;

	for (int i = 1; i <= studentCnt; i++) {
		for (int j = 1; j <= studentCnt; j++) {
			for (int k = 0; k < 4; k++) {
				int nxtR = i + direction[k].first;
				int nxtC = j + direction[k].second;
				if (nxtR < 1 || nxtR > studentCnt || nxtC < 1 || nxtC > studentCnt) {
					continue;
				}

				nearLeft[i][j]++;
			}
		}
	}

	int studentNum;
	int loveNum;
	for (int i = 1; i <= studentCnt*studentCnt; i++) {
		cin >> studentNum;
		studentVec.push_back(studentNum);
		for (int i = 1; i <= 4; i++) {
			cin >> loveNum;
			studentLove[studentNum].push_back(loveNum);
		}
	}

	for (int i = 0; i < studentCnt*studentCnt; i++) {
		int num = studentVec[i];
		go(num);
	}

	for (int i = 1; i <= studentCnt; i++) {
		for (int j = 1; j <= studentCnt; j++) {
			int student = classRoom[i][j];
			int curLove = 0;
			for (int k = 0; k < 4; k++) {
				int nxtR = i + direction[k].first;
				int nxtC = j + direction[k].second;
				if (nxtR < 1 || nxtR > studentCnt || nxtC < 1 || nxtC > studentCnt) {
					continue;
				}

				for (int l = 0; l < 4; l++) {
					if (classRoom[nxtR][nxtC] == studentLove[student][l]) {
						curLove++;
						break;
					}
				}
			}
			ans += addLove[curLove];
		}
	}

	cout << ans;

	return 0;
}

메인함수

처음에 학생수 N을 입력받은 후에,

각 칸마다 범위에 맞게 주변에 빈칸들을 초기화해준다.

그리고나서 학생의 번호와 해당 학생이 좋아하는 4명의 학생의 번호를 입력받고 저장해둔다.

 

그리고 입력받은 학생의 번호순대로 go()메서드를 진행한다.

go()메서드는, 해당 학생이 어디에 앉아야할지 정해주는 메서드이다.

그리고 자리를 다 앉혔으면 각 칸마다 주변에 좋아하는 학생이 몇 명인지에 따라

만족도를 ans에 더해주고 ans를 출력한다.

 

void go(int studentNum) {
	int inputR = 0;
	int inputC = 0;
	int curNearLoveCnt = -1;
	for (int i = 1; i <= studentCnt; i++) {
		for (int j = 1; j <= studentCnt; j++) {
			if (classRoom[i][j] != 0) { continue; }
			else {
				int nearLoveCnt = checkNearLover(studentNum, i, j);
				if ( ( nearLoveCnt > curNearLoveCnt ) || ( curNearLoveCnt == nearLoveCnt &&
					nearLeft[inputR][inputC] < nearLeft[i][j] ) ) {
					inputR = i;
					inputC = j;
					curNearLoveCnt = nearLoveCnt;
				}

			}
		}
	}

	for (int i = 0; i < 4; i++) {
		int nxtR = inputR + direction[i].first;
		int nxtC = inputC + direction[i].second;
		if (nxtR < 1 || nxtR > studentCnt || nxtC < 1 || nxtC > studentCnt) {
			continue;
		}

		nearLeft[nxtR][nxtC]--;
	}

	classRoom[inputR][inputC] = studentNum;
}

학생의 자리를 정해주는 메서드.

위에서 설명했듯이, (1, 1) ~ (N, N)까지 순차적으로 돌면, 3번째 조건은 자동으로 만족된다.

그리고 1번의 조건을 확인하기 위해 탐색중인 칸들 중에서 최대로 주변에 좋아하는 학생이 많은 칸을

저장하기 위해 curNearLoveCnt라는 변수에 최대로 좋아하는 학생의 수를 저장해둔다.

여기서 checkNearLove 메서드는 해당 좌표의 주변에 좋아하는 학생 수가 몇 명인지를 살펴보는 메서드이다.

만일 탐색중인 칸들 중 더 좋아하는 학생이 많은 칸이 나온다면 자리선점을 해당 칸으로 하고,

좋아하는 학생 수는 같은데, 주변에 빈 칸이 더 많은 칸이라면 해당 칸으로 자리를 선점한다.

 

자리선점이 끝나면 그 좌표의 상, 하, 좌, 우칸에 주변빈칸을 저장해두는 배열에 -1씩 해준다.

 

int checkNearLover(int studentNum, int r, int c) {
	int ret = 0;
	for (int i = 0; i < 4; i++) {
		int nxtR = r + direction[i].first;
		int nxtC = c + direction[i].second;
		if (nxtR < 1 || nxtR > studentCnt || nxtC < 1 || nxtC > studentCnt ||
			classRoom[nxtR][nxtC] == 0) {
			continue;
		}

		for (int j = 0; j < 4; j++) {
			if (classRoom[nxtR][nxtC] == studentLove[studentNum][j]) {
				ret++;
				break;
			}
		}
	}
	return ret;
}

해당 칸 주변에 몇 명의 좋아하는 학생이 있는지 살펴보는 메서드

좌표를 매개변수로 입력받고 상, 하, 좌, 우 중에 해당 학생이 좋아하는 학생이 있는지 확인한 후에

ㅁ해당 칸에서는 몇 명의 좋아하는 학생이 인접해있는지 return한다.

 

학생 수를 이상하게 고려해서 런타임 에러가 난 문제.

좀 더 고민해볼걸 아쉽다. 애초에 저걸 생각을 못했다는게 더 아쉬운 문제다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.