BaekJoon 2628번: 종이 자르기

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

2628번: 종이자르기

풀이법

1) 규칙을 찾아 구현함으로서 정답을 얻을 수 있던 문제이다.

2) 가로로 4번 선을 자를 경우, 행 기준 4번 보다 작은 배열의 값들을 모두 1씩 증가시키는 방식으로 문제를 해결하였다. 

문제에서 주어진 다음의 예시의 경우 위의 풀이 방식을 활용하면,

<예시>
10 8
3
0 3
1 4
0 2 

<도출된 자른 배열>
4 4 4 4 3 3 3 3 3 3
4 4 4 4 3 3 3 3 3 3
3 3 3 3 2 2 2 2 2 2
2 2 2 2 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1

 

과 같은 답을 얻을 수 있으며, 총 크기를 구하기 위해서는 bfs 기반의 알고리즘으로 탐색을 진행하여 값을 도출하였다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;
int n, m,t;
int arr[101][101];
bool visited[101][101];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int ans = 0;
void bfs(int a, int b, int val)
{
	int cnt = 0;
	visited[a][b] = true;
	queue<pair<int, int>> q;
	q.push({ a,b });
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();
		cnt++;
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
				continue;
			if (arr[nextX][nextY] == val && !visited[nextX][nextY])
			{
				visited[nextX][nextY] = true;
				q.push({ nextX,nextY });
			}
		}
	}
	ans = max(ans, cnt);
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			arr[i][j] = 1;
		}
	}
	cin >> t;
	for (int p = 0; p < t; p++)
	{
		int a, b;
		cin >> a >> b;
		if (a == 0)
		{
			for (int i = 0; i < b; i++)
			{
				for (int j = 0; j < m; j++)
				{
					arr[i][j]++;
				}
			}
		}
		else//세로
		{
			for (int j= 0; j < b; j++)
			{
				for (int i = 0; i < n; i++)
				{
					arr[i][j]++;
				}
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!visited[i][j])
			{
				bfs(i, j, arr[i][j]);
			}
		}
	}
	cout << ans;

}