백준 2583번 영역 구하기(C++)

문제

정답 코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<utility>
#include<string.h>

using namespace std;
#define X first
#define Y second
int map[102][102];
int mx[4] ={0,1,0,-1};
int my[4] ={1,0,-1,0};
int all;
int result[10000];
// void printmap(int col,int row)
// {
// 	for (int i=col -1; i >= 0;i--)
// 	{
// 		for (int j=0; j < row; j++)
// 		{
// 			cout << map[i][j] << ' ';
// 		}
// 		cout << '\n';
// 	}
// }
int main()
{

	ios :: sync_with_stdio(0);
	cin.tie(0);
	int col,row,snum;
	int lx,ly,rx,ry;
	cin >> col >> row >> snum;
	for(int i=0; i< snum;i++)
	{
		cin >> lx >> ly >> rx >> ry;
		for (int j = ly; j < ry; j++)
		{
			for (int k = lx; k < rx; k++)
				map[j][k] = -1;
		}
	}
	//printmap(col,row);
	queue <pair<int, int> >Q;
	int cnt;
	for (int i=0; i < col; i++)
	{
		for (int j=0; j < row; j++)
		{
			if(map[i][j] != 0)
				continue;
			Q.push({j,i});
			cnt = 1;
			while (!Q.empty())
			{
				auto tmp = Q.front(); Q.pop();
				for (int k = 0; k < 4; k++)
				{
					int myx = tmp.X+mx[k];
					int myy = tmp.Y+my[k];
					if (myx <0 || myy <0 || myx >= row || myy >=col)
						continue;
					if (map[myy][myx] != 0)
						continue;
					cnt++;
					map[myy][myx] = cnt;

					Q.push({myx,myy});
				}
				if (Q.empty())
				{
					if (cnt !=1)
						cnt--;
					result[all] = cnt;
					all++;
				}
			}
		}
	}
	//printmap(col,row);
	cout << all << "\n";
	sort(result,result+all);
	for(int i=0; i< all; i++)
		cout << result[i] << ' ';
}

문제 풀이의 흐름

• 입력을 잘 파싱해서 맵에 입력 받은 부분들의 직사각형에 해당부분을 -1로 초기화 해준다.

• 이제 bfs를 사용해서 계속 맵에다가 결과값을 넣어준다.

• 결과값들을 한번에 담아두고 한번에 출력해준다.

주의 할 점

역시나 bfs는 단순한 조건 문의 실수로 틀릴 가능성이 있다.

반성 및 고찰

• 이 문제는 단순한 bfs문제이다.

• 다만 입력을 파싱하는 부분이 살짝 다른 것 외에는 따로 할 말은 없다.

Uploaded by N2T