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

문제

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

21608번: 상어 초등학교

설명

 

4방향을 계속해서 체크해주면 되는 문제이며 아무 생각 없이 BFS를 떠올리지 말자

또한 여러 우선순위 조건이 있을 때는 Priority_queue를 쓰는 것도 좋은 방법인 것 같다.

 

마지막으로 for문 여러 개 중첩 시 순서를 잘 설계하고 코드 구현에 들어가자!! (+배열 인덱스 주의)

 

 

 

코드 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N;
int map[21][21];
bool visited[21][21];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };

struct Student {
	int num;
	int arr[4];

};
Student human[2000];
struct ABC {
	int blank;
	int like_num;
	int r;
	int c;

};
struct cmp {
	bool operator()(ABC a,ABC b) {
		//1,2,3 각각 우선순위 배정
		if (a.like_num == b.like_num) {

			if (a.blank == b.blank) {
				if (a.r == b.r) {
					return a.c > b.c;
				}

				return a.r > b.r;
			}
			return a.blank < b.blank;
		}
		return a.like_num < b.like_num;
	}
};
priority_queue<ABC, vector<ABC>, cmp> pq;
void findSit(int y,int x,int k) {
	int like_cnt = 0;
	int blank_cnt = 0;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		for (int j = 0; j < 4; j++) {
			if (map[ny][nx] == human[k].arr[j]) {
				like_cnt++;
			}
		}
		
		if (map[ny][nx] == 0) {
			blank_cnt++;
		}
	}

	pq.push({ blank_cnt,like_cnt,y,x });

}
int main() {
	cin >> N;

	for (int i = 0; i < N * N; i++) {
		cin >> human[i].num;
		for (int j = 0; j < 4; j++) {
			cin >> human[i].arr[j];
		}

	}

	for (int i = 0; i < N * N; i++) {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (map[y][x] == 0) {
					findSit(y, x,i);
				}
			}
			
		}
		map[pq.top().r][pq.top().c] = human[i].num; //자리배정완료 
		//pq초기화 까먹지말자
		while (!pq.empty()) {
			pq.pop();
		}

	}
	//만족도조사
	int answer = 0;
	
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				int score = 0;
				for (int i = 0; i < N * N; i++) {
					if (map[y][x] == human[i].num) {

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

					}
				}

				if (score == 1) answer += 1;
				if (score == 2) answer += 10;
				if (score == 3) answer += 100;
				if (score == 4) answer += 1000;

			}

		}



	


	cout << answer;

	return 0;
}