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

리뷰

 

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

빡구현 문제.. 설계를 초반에 잘 하고 넘어가야 코드 수정하는 일이 적어질 것 같다.

for문, while문의 지옥을 맛본 문제

 

 

전역 변수

• n : 주어지는 공간의 한 변의 길이
• lst : 주어지는 2차원 공강을 저장하기 위한 정수형 2차 배열
• dx, dy : 상하좌우 탐색을 위한 방향 배열
• friends : 좋아하는 친구 번호를 저장하기 위한 정수형 벡터 배열
• Pos : 각 학생의 존재 여부와 좌표를 저장하기 위한 구조체
• poses : 학생 번호를 인덱스로 관리하기 위한 Pos타입 배열
• Prio : 학생을 배치할 때 우선순위로 사용하기 위한 구조체, 주변 친구의 수 c순으로 내림차순, 주변 빈칸의 수 e순으로 내림차순, 행 번호 x순으로 오름차순, 열 번호 y순으로 오름차순 해준다.

 

함수

1. no_friends

void no_friends(int now)

 

좋아하는 친구가 맵 상에 없을 때 학생을 배치하기 위한 함수

1. 현재 학생의 번호를 매개변수now로 입력 받는다.
2. Prio타입의 우선순위 큐 pq를 초기화 해준다.
3. n * n맵을 탐색하며 아직 학생이 배치되지 않은 빈 칸을 찾은 경우 로직을 실행한다.
4. 빈 칸의 개수를 셀 변수 emp를 0으로 초기화 해준다.
5. 현재 위치에서 4방향을 탐색하고 빈 칸이 있다면 emp를 증가 시켜준다.
6. 4방향 탐색이 끝난 후 현재 x, y좌표와 emp값을 pq에 push해준다.
7. pq의 top에 존재하는 위치로 학생을 배치해 준다.
8. 학생을 배치할땐 poses의 now인덱스에 학생의 좌표와 존재여부 1을 넣어준다.
9. 맵에서는 학생의 좌표에 now를 기록해 주면 된다.

 

2. solve

void solve(int now)

 

학생과 그 학생의 좋아하는 학생의 번호를 입력 받고 맵에서의 배치 구현을 위한 함수

1. Prio타입 우선순위 큐 pq를 초기화 해준다.
2. 좋아하는 친구 4명의 번호를 입력 받아 friends 벡터 배열의 now인덱스에 4명의 친구를 추가해 준다.
3. 4며으이 친구를 순회한다, 만약 poses 배열의 친구의 e가 1이라면 현재 맵에 존재하는 친구이다.
4. 친구가 맵 상에 존재한다면 해당 친구의 좌표를 가져와 4방향에 빈칸이 있는지 체크한다.
5. 빈칸이 있다면 해당 빈칸에서 또 다시 4방향을 탐색하여 인접한 친구 수와 빈 칸을 체크한다.
6. 빈 칸은 emp, 친구 수는 cnt에 저장하여 pq에 들어갈 수 있는 위치와 emp, cnt를 추가해준다.
7. 만약 pq가 비었다면 적절하게 친구 옆에 배치될 수 없는 상태이다 no_friends 함수를 실행해 준다.
8. pq가 비지 않았다면 pq의 top에 위치한 좌표에 학생을 배치하고 존재함을 표시해 준다.

 

3. print

void print()

 

디버깅용 함수로, friends와 맵 정보를 체크하기 위해 사용하였다.

 

4. calc

int calc()

 

맵 배치가 끝난 후 정답을 출력하기 위해 사용하는 함수

1. 정수형 변수 result를 0으로 초기화 해준다.
2. n * n 맵을 순회 하며 각 배치된 학생의 입장에서 좋아하는 친구와 얼마나 붙어있는지 체크해 준다.
3. 정수형 변수 cnt를 0으로, now를 맵 상에서의 현재 위치의 값(학생 번호)으로 저장한다.
4. 해당 학생에서 4방향을 탐색하며 좋아하는 친구를 찾을 때마다 cnt를 증가시켜 준다.
5. cnt가 4라면 1000을, 3이면 100, 2면 10, 1이면 1을 result에 더해준다.
6. 맵 상의 모든 학생 탐색을 마친 후에 result에 저장된 값을 리턴해 준다.

 

문제풀이

1. n값을 입력 받고, n * n번의 반복문을 통해 학생 번호를 입력 받는다.
2. 입력 받은 학생 번호를 solve함수의 매개변수로 전달하여 함수를 실행해 준다.
3. 학생 배치가 끝난 후 calc 함수를 실행하여 리턴 받은 값을 출력해 준다.

 

참고 사항

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

먼저 맵 상에 좋아하는 친구가 있는지 체크 후 존재 한다면 주변에 들어갈 칸이 있는지를 체크해 주어야 한다.

들어갈 수 있다면 그 안에서 2, 3번 조건을 체크해 준다.

만약 맵 상에 좋아하는 친구가 없다면 모든 맵을 순회하며 2, 3번 조건에 맞는 위치를 찾아야 한다.

 

 

정답 코드

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

int n;
int lst[21][21];
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };
vector<int> friends[401];

struct Pos {
	int x, y, e;
};
Pos poses[401];

struct Prio {
	int x, y, e, c;
	bool operator<(const Prio& other) const {
		if (c < other.c) return true;
		if (c > other.c) return false;
		if (e < other.e) return true;
		if (e > other.e) return false;
		if (x > other.x) return true;
		if (x < other.x) return false;
		return y > other.y;
	}
};

void no_friends(int now) {
	priority_queue<Prio> pq;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (!lst[i][j]) {
				int emp = 0;
				for (int k = 0; k < 4; ++k) {
					int nx = i + dx[k], ny = j + dy[k];
					if (0 < nx && nx <= n && 0 < ny && ny <= n && !lst[nx][ny]) emp++;
				}
				pq.push({ i, j, emp });
			}
		}
	}
	Prio prio = pq.top();
	poses[now] = { prio.x, prio.y, 1 };
	lst[prio.x][prio.y] = now;
}

void solve(int now) {
	priority_queue<Prio> pq;
	for (int i = 0; i < 4; ++i) {
		int f; cin >> f;
		friends[now].push_back(f);
	}

	for (int i = 0; i < 4; ++i) {
		int f = friends[now][i];
		if (poses[f].e) {
			int cx = poses[f].x, cy = poses[f].y;
			for (int j = 0; j < 4; ++j) {
				int nx = cx + dx[j], ny = cy + dy[j];
				if (0 < nx && nx <= n && 0 < ny && ny <= n && !lst[nx][ny]) {
					int cnt = 0, emp = 0;
					for (int k = 0; k < 4; ++k) {
						int nnx = nx + dx[k], nny = ny + dy[k];
						if (0 < nnx && nnx <= n && 0 < nny && nny <= n) {
							if (!lst[nnx][nny]) {
								emp++;
								continue;
							}
							auto it = find(friends[now].begin(), friends[now].end(), lst[nnx][nny]);
							if (it != friends[now].end()) cnt++;
						}
					}
					pq.push({ nx, ny, emp, cnt });
				}
			}
		}
	}

	if (pq.empty()) no_friends(now);
	else {
		Prio prio = pq.top();
		poses[now] = { prio.x, prio.y, 1 };
		lst[prio.x][prio.y] = now;
	}
}

void print() {
	cout << "\n";
	for (int i = 1; i <= n * n; ++i) {
		for (int j : friends[i]) cout << j << " ";
		cout << "\n";
	}

	cout << "\n";
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cout << lst[i][j] << " ";
		}
		cout << "\n";
	}
}

int calc() {
	int result = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			int cnt = 0;
			int now = lst[i][j];
			for (int k = 0; k < 4; ++k) {
				int nx = i + dx[k], ny = j + dy[k];
				if (0 < nx && nx <= n && 0 < ny && ny <= n) {
					auto it = find(friends[now].begin(), friends[now].end(), lst[nx][ny]);
					if (it != friends[now].end()) cnt++;
				}
			}
			if (cnt == 4) result += 1000;
			else if (cnt == 3) result += 100;
			else if (cnt == 2) result += 10;
			else if (cnt == 1) result += 1;
		}
	}
	return result;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n * n; ++i) {
		int s; cin >> s;
		solve(s);
	}
	//print();
	cout << calc();
}