[210329][백준/BOJ] 2583번 영역 구하기

문제

입출력

---

풀이

모눈종이에 k 개의 직사각형을 그리고 이 직사각형으로 분리되는 영역이 몇개인지를 구하는 문제이다.

1. 모눈종이의 크기를 나타내는 m, n 직사각형을 개수를 나타내는 k를 입력받는다.
2. 직사각형의 왼쪽 아래 x, y 좌표값과 오른쪽 위 x, y의 좌표값을 입력받는데 이를 이중 for문의 시작, 종료값으로 설정해서 모눈종이에 그린다.
3. 그림 1을 우리가 알고 있는 배열에 맞게 오른쪽으로 한바퀴 돌리면 아래와 같은 모습이 된다.
   
4. 따라서 n이 행이 되고 m이 열이 된다.
5. bfs를 이용해서 문제를 풀고 이를 출력해보면 아래와 같다.
   
6. 총 영역의 개수와 각 영역의 크기는 지금까지 푼 방식으로 해결하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define SIZE 102

int board[SIZE][SIZE];
bool vis[SIZE][SIZE];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int m, n, k, x1, y1, x2, y2;

	cin >> m >> n >> k;

	for (int i = 0; i < k; ++i)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j1 = x1; j1 < x2; ++j1)
		{
			for (int j2 = y1; j2 < y2; ++j2)
				board[j1][j2]++;
		}
	}

	int num = 0; // 위치의 갯수
	vector<int> V; // 각 위치의 크기 저장하는 배열
	
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (vis[i][j] || board[i][j] != 0) continue;
			num++;
			queue<pair<int, int>> Q;
			Q.push({ i,j });
			vis[i][j] = 1;

			int area = 0; // 각 위치의 크기

			while (!Q.empty())
			{
				area++;
				auto cur = Q.front(); Q.pop();
				for (int dir = 0; dir < 4; ++dir)
				{
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
					if (vis[nx][ny] || board[nx][ny] != 0)continue;
					vis[nx][ny] = 1;
					Q.push({ nx,ny });
				}
			}
			V.push_back(area);
		}
	}

	cout << num << '\n';
	sort(V.begin(), V.end());
	for (auto e : V)
		cout << e << '\n';
        
	/*for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (board[i][j] == 2)
				board[i][j] = 1;
			cout << board[i][j] << ' ';
		}
		cout << '\n';
	}	*/
}

---

느낀점

예제 케이스도 맞고 여러가지 반례도 다 맞아서 자신있게 코드를 제출했는데 채점 결과가 틀렸습니다가 계속 나왔다. 이는

if (vis[i][j] || board[i][j] != 0) continue;

모눈종이가 색칠해져있는 부분을 위의 코드로 찾아야하는데

if (vis[i][j] || board[i][j] == 1 || board[i][j] == 2) continue;

로 해서 틀린거였다. 직사각형이 단 두번까지만 쌓이는것도 아닌데 섣부르게 이를 판단하였다.
이런 사소하지만 치명적인 실수들을 자주 하는거 같다. 조금 더 섬세해질 필요가 있어보인다.

bfs 문제를 계속 풀다보니 몇가지 조심해야할 점들이 보인다.

1. 시작점이 몇개인지 가장 먼저 파악해야 한다. 시작점이 한개 인지, 여러개 인지, 여러개가 동시에 실행되어야 하는지, 순서대로 실행되어도 되는지.. 이를 잘 파악하고 코드를 짜야한다.
2. 입력받는 행과 열을 잘 구분해야한다. 행과 열의 크기가 다를 경우에는 어떤 값이 행인지, 열인지가 중요하므로 이를 잘 신경써야한다.
3. 인접한 원소에 접근하는 조건을 잘 설정해야한다. 특히 입력이 문자열이였다면 0이 아닌 '0'으로 구분해야한다.

아직까지 엄청 어려운 문제를 푼 것은 아니다. bfs가 어떤것인지 맛을 보면서 점점 정답률이 낮은 문제에 도전해봐야겠다. 구현이 안되더라도 어떠한 로직으로 접근해야 하는지라도 생각을 해보면 좋을거 같다.