5653. [모의 SW 역량테스트] 줄기세포배양

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE#

SW Expert Academy

 

map에 구조체를 키나 데이터로 사용하는 방법은 정렬 기준이 있어야 함.

map은 트리 구조 이므로 key searching 필요

 

구조체 내에 operator 선언해 주어야 하는데 신기한 점은 괄호 앞에 const 붙여야됨. 

 

 

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

using namespace std;
int N, M, K;

struct Pos
{
	int y;
	int x;

	bool operator<(const Pos& n)const{
		if (y != n.y)
		{
			return y < n.y;
		}
		return x < n.x;

	}
};

struct Node {
	int y;
	int x;
	int cost;
	int cur;
	int time;

	bool operator<(const Node& e)
	const{
		if (time != e.time)
		{
			return time > e.time;
		}

		return cost < e.cost;
	}
};

map<Pos, bool> m;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		m.clear();
		priority_queue<Node> que;
		cin >> N >> M >> K;
		
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				int a;
				cin >> a;
				if (a)
				{
					Node n = { i,j };
					m[{i, j}] = true;
					que.push({ i,j,a,a,0 });

				}
			}
		}
		

		
		while (!que.empty())
		{
			int y = que.top().y;
			int x = que.top().x;
			int cost = que.top().cost;
			int cur = que.top().cur;
			int time = que.top().time;


			

			if (time >= K)
			{
				break;
			}

			que.pop();
			cur--;
			time++;

			if (cur < 0)
			{
				if (cur == -1)
				{
					

					if (!m[{y + 1, x}])
					{
						m[{y + 1, x}] = true;
						que.push({ y + 1,x,cost,cost,time });

					}

					if (!m[{y - 1, x}])
					{
						m[{y - 1, x}] = true;
						que.push({ y - 1,x,cost,cost,time });
					}

					if (!m[{y, x + 1}])
					{
						m[{y, x + 1}] = true;
						que.push({ y,x + 1,cost,cost,time });
					}

					if (!m[{y, x - 1}])
					{
						m[{y, x - 1}] = true;
						que.push({ y,x - 1,cost,cost,time });
					}
				}

				if (abs(cur) < cost)
				{
					que.push({ y,x,cost,cur,time });
				}
				
			}
			else if(cur >= 0)
			{
				que.push({ y,x,cost,cur,time });
			}
		}
		
		int result = que.size();

		cout << "#" << test_case << " " << result << endl;


	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}