백준 17140번 _ 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

 

1. 풀이방법

 

 이 문제는 주요함수하나만 제대로 짠다면 그리 문제가 될일은 없기 때문에 Rcalculate라는 함수에서 문제가 될 부분만 설명하겠다.

bool compare(const pair<int, int>& a, const pair<int, int>& b)
{
	if (a.second == b.second)
		return a.first < b.first;
	return a.second < b.second;
}

vector<pair<int, int>> tmp;
for (auto& changeValue : Rmap)
	tmp.push_back({ changeValue.second.first, changeValue.second.second });
sort(begin(tmp), end(tmp), compare);

 바로 이 부분이다. map에서 받아온 데이터들을 vector에 넣고 숫자의 개수가 작은순, 숫자의 크기가 작은순으로 배열한다. 이 부분만 정확히 잘 짠다면 이 문제를 푸는데 있어 큰 문제가 될 부분은 없다고 보여진다.

 

 나는 map -> vector에서 sort -> place에 넣기 이렇게 구현했지만, map 자체에 비교함수를 작성해서 map -> place 이렇게 하면 시간을 줄일수 있을거 같다. 사실 처음에는 후자로 구현하기 위해서 여러 자료들을 구글에서 찾아보았는데 나에겐 좀많이 까다로웠다. ㅠ 지금도 찾아보고 있는 중인데 완전히 이해되면 추가적으로 포스팅 하겠다.

 

---

 

2. 코드

 

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int place[102][102];
int r, c, k;
int R = 3, C = 3;

bool compare(const pair<int, int>& a, const pair<int, int>& b)
{
	if (a.second == b.second)
		return a.first < b.first;
	return a.second < b.second;
}

void Rcalculate()
{
	map<int, pair<int, int>> Rmap;
	int changeC = 0;
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			if (place[i][j] == 0)
				continue;

			if (Rmap.count(place[i][j]) == 0)
				Rmap.insert({ place[i][j], { place[i][j], 1 } });

			else
				Rmap[place[i][j]] = { Rmap[place[i][j]].first, Rmap[place[i][j]].second + 1 };

			place[i][j] = 0;
		}

		//이부분을 map 비교함수로 작성한다면 속도를 매우 줄일수 있음
		vector<pair<int, int>> tmp;
		for (auto& changeValue : Rmap)
			tmp.push_back({changeValue.second.first, changeValue.second.second});
		sort(begin(tmp), end(tmp), compare);
		
		int idx = 1;
		for (auto& changeValue : tmp)
		{
			if (idx > 100)
				break;
			place[i][idx++] = changeValue.first;
			if (idx > 100)
				break;
			place[i][idx++] = changeValue.second;
		}
		changeC = max(changeC, idx - 1);
		Rmap.clear();
	}
	C = changeC;
}

void Ccalculate()
{
	map<int, pair<int, int>> Cmap;
	int changeR = 0;
	for (int j = 1; j <= C; j++)
	{
		for (int i = 1; i <= R; i++)
		{
			if (place[i][j] == 0)
				continue;
			if (Cmap.count(place[i][j]) == 0)
				Cmap.insert({ place[i][j], { place[i][j], 1 } });

			else
				Cmap[place[i][j]] = { Cmap[place[i][j]].first, Cmap[place[i][j]].second + 1 };

			place[i][j] = 0;
		}

		//이부분을 map 비교함수로 작성한다면 속도를 매우 줄일수 있음
		vector<pair<int, int>> tmp;
		for (auto& changeValue : Cmap)
			tmp.push_back({ changeValue.second.first, changeValue.second.second });
		sort(begin(tmp), end(tmp), compare);

		int idx = 1;
		for (auto& changeValue : tmp)
		{
			if (idx > 100)
				break;
			place[idx++][j] = changeValue.first;
			if (idx > 100)
				break;
			place[idx++][j] = changeValue.second;
		}
		changeR = max(changeR, idx - 1);
		Cmap.clear();
	}
	R = changeR;
}

void Input()
{
	cin >> r >> c >> k;
	int value;
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			cin >> value;
			place[i][j] = value;
		}
	}
}

bool isSucess()
{
	//check map
	if (place[r][c] == k)
		return true;
	return false;
}

int solve()
{
	if (isSucess())
		return 0;

	int cnt = 0;
	while (1)
	{
		if (cnt > 100)
			return -1;
		if (R >= C)
			Rcalculate();
		else
			Ccalculate();

		cnt++;
		
		if (isSucess())
			break;
	}
	return cnt;
}

int main()
{
	Input();
	cout <<solve();
	return 0;
}

 

 

---

 

3. 후기

 

 조금 쉬운 문제이긴 했지만 한번에 구현되서 기분이 좋았다.