16924 십자가 찾기

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

16924번: 십자가 찾기

십자가 찾기 성공스페셜 저지

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

660

265

202

40.726%

문제

십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크거나 같아야 한다.

아래 그림은 크기가 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.

...*... ..*.. ...*... .*. ..*.. ...*... *** ***** ******* .*. ..*.. ...*... ..*.. ...*... ...*...

크기가 N×M이고, '.'과 '*'로 이루어진 격자판이 주어진다. 이때, 십자가만을 이용해서 격자판과 같은 모양을 만들 수 있는지 구해보자. 십자가는 서로 겹쳐도 된다. 사용할 수 있는 십자가의 개수는 N×M이하이어야 한다. 격자판의 행은 위에서부터 1번, 열은 왼쪽에서부터 1번으로 번호가 매겨져 있다.

입력

첫째 줄에 격자판의 크기 N, M (3 ≤ N, M ≤ 100)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다.

출력

십자가만 이용해서 입력으로 주어진 격자판을 만들 수 없으면 -1을 출력한다.

만들 수 있는 경우에는 필요한 십자가의 수 k(0 ≤ k ≤ N×M)를 출력한다. 다음 k개의 줄에는 그려야 하는 십자가의 정보 x, y, s를 한 줄에 하나씩 출력한다. x는 십자가 중심의 행의 번호, y는 열의 번호, s는 십자가의 크기이다.

가능한 답이 여러가지인 경우에는 아무거나 출력한다.

 

 

풀이)

 

1.)  풀이한 시간복잡도는  십자가의 중심의 '*'을 찾는데 O(N-2*M-2 * size) +

    *에서 size 크기 최대(100 == N,M) 를 찾는부분과, 십자가 좌표의 벡터 탐색의 O(N) +

    두번째 배열의 십자가를 그리는 N*M

O [ (N-2*M-2*size) + vector.size() +  N*M] 으로 이하 O[NMSIZE = O(N^3) 으로 하였다

N과 M의 최대범위 100^3은 1,000,000이다. 

 

2. 십자가의 위치를 찾는부분은 십자가의 중심을 찾으면 됨으로

    2차원 배열의 사이드 부분은 탐색하지 않아도 된다. O(N-2 * M-2)

 

3. 탐색을하며 *을 찾으면 해당 좌표에서 십자가가 형성되어 있는지 살펴본다 (4방향 탐색)

 

4. 십자가가 형성되었다면 사이즈를 찾는다.

 

5. 십자가의 좌표 (x,y) 와 size를 vector<pair<pair<x,y>>,size> 에 담는다.

 

6. 해당 십자가가 완성형 십자가인지 (반례 : 예제3 같은십자가는 안됨.)

   검사하기 위해 두번째 배열 코드의 arr_2[100][100] 에 똑같이 그려본다.

 

7. 일치한다면 개수와 좌표를 출력한다.

 

#include<iostream>
#include<vector>

using namespace std;
char arr[100][100];
char arr_2[100][100];
int N, M;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int check_cross(int x, int y);
int main(void)
{
	cin >> N >> M;
	// 격자 만들기
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> arr[i][j];
			arr_2[i][j] = arr[i][j];
			if (arr_2[i][j] == '*') arr_2[i][j] = '.';
		}
	}
	//격자 탐색
	vector<pair<pair<int, int>, int>> v;
	for (int i = 1; i < N; ++i)
	{
		for (int j = 1; j < M; ++j)
		{
			// *이 있는곳을 탐색 ( 십자가 체크 : continue)
			if (arr[i][j] == '*')
			{
				int cross_size = check_cross(i, j);
				if (cross_size > 0)
				{
					v.push_back(make_pair(make_pair(i + 1, j + 1), cross_size));
				}
				
			}
		}
	}
	//십자가가 없는경우
	if (v.size() == 0)
	{
		cout << -1 << '\n';
		return 0;
	}
	else//찾은 십자가가 있음, 실제 arr_2배열에 십자가를 그려보고 비교
	{
		
		//vector에 담은 좌표를 arr_2에 십자가 그림.
		for (int i = 0; i < v.size(); ++i)
		{
			int x = v[i].first.first -1;
			int y = v[i].first.second -1;
			arr_2[x][y] = '*';
			int size = v[i].second;

			for (int k = 1; k <= size; ++k)
			{
				for (int j = 0; j < 4; ++j)
				{
					int xn = x + (k * dx[j]);
					int yn = y + (k * dy[j]);
					arr_2[xn][yn] = '*';
				}
			}
		}
		//arr_2의 십자가와 arr 의 십자가의
		//모든 원소를 비교하여 하나라도 다르면 만들 수 없음.
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < M; ++j)
			{
				if (arr[i][j] != arr_2[i][j])
				{
					cout << -1 << '\n';
					return 0;
				}
			}
		}
		int ans_cnt = 0;
		for (int i = 0; i < v.size(); ++i)
		{
			ans_cnt += v[i].second;
		}
		cout << ans_cnt << '\n';
		// 다 똑같다면 좌표를 출력.
		for (int i = 0; i < v.size(); ++i)
		{
			int x = v[i].first.first;
			int y = v[i].first.second;
			int size = v[i].second;
			for (int j = size; j > 0; j--)
			{
				cout << x << ' ' << y << ' ' << j << '\n';
			}
		}
	}
	return 0;
}
int check_cross(int x, int y)
{
	int cnt = 0;

	for (int size = 1; size < 100; ++size)
	{
		bool isable = true;
		for (int i = 0; i < 4; ++i)
		{
			int xn = x + (size*dx[i]);
			int yn = y + (size*dy[i]);

			if (xn >= N || xn < 0 || yn >= M || yn < 0)
			{
				isable = false;
				break;
			}

			if (arr[xn][yn] != '*')
			{
				isable = false;
			}
				
		}
		if (!isable)  break;
		cnt += 1;
	}

	return cnt;
}