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

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

21608번: 상어 초등학교

코드 설명 

지독한 구현 문제이다 삼성 문제는 구조체를 통해 담아두는 게 중요한 것 같다. 그리고 시간이 걸리더라도 설계를 최대한 상세하게 완벽하게 해 주는 것이 좋은 것 같다...(이번 문제 같은 경우 for문 속의 for문이 너무도 많기 때문에 작성하다가 놓친다)

 

우선순위 큐를 구현해서 문제에서 나온 우선순위대로 구현해준다.

map을 전체 탐색 하면서 0인 경우 들어가서 주변에 빈칸이 있는지++ , 좋아하는 친구가 있는지 ++ 체크해서 우선순위 큐에 넣어준다.

 

이후 마지막에 만족도 검사를 하면 된다

 

코드

#include<vector>
#include<iostream>
#include<queue>
using namespace std;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int map[501][501];
bool visited[501][501];
struct human {
	int idx;
	int like[4];
	int y;
	int x;
};
struct pp {
	int y;
	int x;
	int blankcnt;
	int friendcnt;
};
struct cmp {
	bool operator()(pp a,pp b) {
		if (a.friendcnt == b.friendcnt) {
			if (a.blankcnt == b.blankcnt) {
				if (a.y == b.y) {
					return a.x > b.x;
				}
				return a.y > b.y;
			}
			
			return a.blankcnt < b.blankcnt;
		}

		return a.friendcnt < b.friendcnt;
	}

};
int jumsu[5] = { 0,1,10,100,1000 };
int N;
vector<human> child;
int main() {
	cin >> N;

	for (int i = 0; i < N * N; i++) {
		int a, b, c, d, e;
		cin >> a >> b >> c >> d >> e;
		child.push_back({ a,{b,c,d,e},0,0 });
		//놓일 자리 탐색	
		

	}

	for (int i = 0; i < child.size(); i++) {
	
		priority_queue<pp, vector<pp>, cmp> pq;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (map[y][x] == 0) {
					int blank_cnt = 0;
					int friend_cnt = 0;
					for (int k = 0; k < 4; k++) {
						int ny = y + dy[k];
						int nx = x + dx[k];
						if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
						if (map[ny][nx] == 0) {
							blank_cnt++;
						}
						else {
							for(int j=0;j<4;j++){
								if (map[ny][nx] == child[i].like[j]) {
									friend_cnt++;
									break;
								}
							}
						}

					}


				pq.push({ y,x,blank_cnt,friend_cnt });
				}
			}
		}
		if (!pq.empty()) {
			int dy = pq.top().y;
			int dx = pq.top().x;
			
			map[dy][dx] = child[i].idx;
			child[i].y = dy;
			child[i].x = dx;

		}

	}

	//만족도 조사 
	int res = 0;
	for (int i = 0; i < N * N; i++) {
		int y = child[i].y;
		int x = child[i].x;

		int friends = 0;
		for (int k = 0; k < 4; k++) {
			int ny = y + dy[k];
			int nx = x + dx[k];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			for (int j = 0; j < 4; j++) {
				if (map[ny][nx] == child[i].like[j]) {
					friends++;
					break;
				}

			}
		}
		res += jumsu[friends];
	}
	cout << res;


	return 0;
}