16234 Samsung sw test

์ฝ”๋“œ

#include <iostream>
#include <list>
#include <cstring>
#define MAX_WIDTH 50
 
using namespace std;
 
typedef struct Location {
	int row;
	int col;
} Location;
 
int map[MAX_WIDTH][MAX_WIDTH];
int tempMap[MAX_WIDTH][MAX_WIDTH];
int width, lowerBound, upperBound;
bool visit[MAX_WIDTH][MAX_WIDTH];
 
int getCountOfImmigration();
bool checkNeibor(Location l, int way);
void movePeople(Location l);
 
int main() {
	cin >> width >> lowerBound >> upperBound;
	for (int i = 0; i < width; i++)
		for (int j = 0; j < width; j++)
			cin>>map[i][j];
 
	cout << getCountOfImmigration();
}
 
int getCountOfImmigration() {
	int count = 0;
	bool check = true;
	for (int i = 0; i < width; i++)
		memcpy(tempMap[i], map[i], sizeof(int) * width);
 
	while (check) {
		check = false;
		bool check2 = false;
		for (int i = 0; i < width; i++)
			memset(visit[i], 0, sizeof(bool) * width);
 
		for (int i = 0; i < width; i++)
			for (int j = 0; j < width; j++) {
				if (visit[i][j])
					continue;
				if (i > 0 && checkNeibor({ i, j }, 0)) {
					movePeople({ i,j });
					count += check2 ? 0 : 1;
					check = true;
					check2 = true;
				}
				else if (j < width -1 && checkNeibor({ i, j }, 1)) {
					movePeople({ i,j });
					count += check2 ? 0 : 1;
					check = true;
					check2 = true;
				}
				else if (i < width - 1 && checkNeibor({ i, j }, 2)) {
					movePeople({ i,j });
					count += check2 ? 0 : 1;
					check = true;
					check2 = true;
				}
				else if (j > 0 && checkNeibor({ i, j }, 3)) {
					movePeople({ i,j });
					count += check2 ? 0 : 1;
					check = true;
					check2 = true;
				}
			}
 
		for (int i = 0; i < width; i++)
			memcpy(map[i], tempMap[i], sizeof(int) * width);
 
	}
 
	return count;
}
 
 
bool checkNeibor(Location l, int way) {
	if (l.row > 0 && way == 0) {
		int d = map[l.row][l.col] - map[l.row - 1][l.col];
		d = d < 0 ? (-1) * d : d;
		if (d >= lowerBound && d <= upperBound)
			return true;
	}
	else if (l.row < width - 1 && way == 2) {
		int d = map[l.row][l.col] - map[l.row + 1][l.col];
		d = d < 0 ? (-1) * d : d;
		if (d >= lowerBound && d <= upperBound)
			return true;
	}
	else if (l.col > 0 && way == 3) {
		int d = map[l.row][l.col] - map[l.row][l.col - 1];
		d = d < 0 ? (-1) * d : d;
		if (d >= lowerBound && d <= upperBound)
			return true;
	}
	else if (l.col < width - 1 && way == 1) {
		int d = map[l.row][l.col] - map[l.row][l.col + 1];
		d = d < 0 ? (-1) * d : d;
		if (d >= lowerBound && d <= upperBound)
			return true;
	}
 
	return false;
}
 
void movePeople(Location l) {
	bool tempVisit[MAX_WIDTH][MAX_WIDTH] = { 0, };
	list<Location> q;
	q.push_back({ l.row, l.col });
 
	list<Location> temp;
	temp.push_back({ l.row, l.col });
	tempVisit[l.row][l.col] = true;
	visit[l.row][l.col] = true;
	while (!temp.empty()) {
		Location t = temp.front();
		temp.pop_front();
		if (!tempVisit[t.row - 1][t.col] && checkNeibor(t, 0)) {
			temp.push_back({ t.row - 1, t.col });
			q.push_back({ t.row - 1, t.col });
			tempVisit[t.row - 1][t.col] = true;
			visit[t.row - 1][t.col] = true;
		}
		if (!tempVisit[t.row][t.col + 1] && checkNeibor(t, 1)) {
			temp.push_back({ t.row, t.col +1});
			q.push_back({ t.row, t.col +1});
			tempVisit[t.row][t.col + 1] = true;
			visit[t.row][t.col + 1] = true;
		}
		if (!tempVisit[t.row + 1][t.col] && checkNeibor(t, 2)) {
			temp.push_back({ t.row+1, t.col });
			q.push_back({ t.row+1, t.col });
			tempVisit[t.row+1][t.col] = true;
			visit[t.row + 1][t.col] = true;
		}
		if (!tempVisit[t.row][t.col - 1] && checkNeibor(t, 3)) {
			temp.push_back({ t.row, t.col - 1 });
			q.push_back({ t.row, t.col - 1 });
			tempVisit[t.row][t.col - 1] = true;
			visit[t.row][t.col - 1] = true;
		}
	}
 
	int count = 0;
	list<Location>::iterator iter;
	for (iter = q.begin(); iter != q.end(); iter++)
		count += map[(*iter).row][(*iter).col];
 
	int people = count / q.size();
 
	for (iter = q.begin(); iter != q.end(); iter++) {
		tempMap[(*iter).row][(*iter).col] = people;
	}
}