[boj][c++] 1012 유기농배추, 11286 절댓값힙

1012 유기농 배추

graph와 visit배열을 따로 만들어서 한번 처리한 값을 다시 처리하지 않도록 함
queue사용해서 너비우선탐색 연산으로 붙어있는 배추를 하나의 묶음으로 처리함

#include	<iostream>
#include	<cstring>
#include	<queue>
using namespace std;

int t, m, n, k, x, y, cnt;
int graph[51][51];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool visit[51][51];

void bfs(int y, int x)
{
	queue<pair<int, int>>q;
	visit[y][x] = true;
	q.push({ x,y });
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if ((nx >= 0 && nx < m) && (ny >= 0 && ny < n) \
            	&& graph[ny][nx] == 1 && visit[ny][nx] == false)
			{
				visit[ny][nx] = true;
				q.push({ nx,ny });
			}
		}
	}
}

int main()
{
	cin >> t;
	while (t--)
	{
		memset(graph, 0, sizeof(graph));
		memset(visit, false, sizeof(visit));
		cin >> m >> n >> k;
		cnt = 0;
		for (int i = 0; i < k; i++)
		{
			cin >> x >> y;
			graph[y][x] = 1;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (graph[i][j] == 1 && visit[i][j] == false)
				{
					bfs(i, j);
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
}

11286 절댓값 힙

queue 컨테이너에 내장된 priority queue(우선순위큐)를 사용하는 문제였다. 절댓값으로 비교해야 하고 내림차순으로 정렬되는 우선순위큐의 특성상 오름차순 정렬을 사용하기 위해서 몇가지 장치를 준비해야 했다.

priority_queue<int, vector<int>, greater<int>> q;

위와 같은 방법을 이용했으나 절댓값도 추가로 저장해야 하므로 pair를 사용했다. 그래서 내가 사용한 우선순위 큐는 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> q 라는 다소 난해한 식이 나왔다.

#include	<iostream>
#include	<cmath>
#include	<queue>
using namespace std;

int n, x;
priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

int main()
{
	cin >> n;
	while (n--)
	{
		cin >> x;
		if (x == 0)
		{
			if (!q.empty())
			{
				cout << q.top().second << "\n";
				q.pop();
			}
			else
				cout << 0 << "\n";
		}
		else
		{
			q.push({ abs(x),x });
		}
	}
}

class 3

solved class 3 달성했다. 게임 시스템에 진심인