[백준] 16924 십자가 찾기

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

16924번: 십자가 찾기

 

시뮬레이션 문제이다.

 

1. 맵에서 현재탐색 위치인 (y, x)가 * 이라고 할때, (y, x-1) 과 (y, x+1) 도 * 인 블록을 찾는다.

2. (y, x)를 기준으로 하는 십자가를 생성할 수 있는 지 확인하고 가능하다면 visit 배열에 십자가를 표시한다.

3. 십자가의 크기와 y, x 를 벡터에 넣어준다.

4. 맵의 모든 블록을 1~3 의 과정으로 탐색해준다.

5. visit 배열과 맵을 비교하여 일치하는 지 확인한다.

6. 일치하지 않는다면 -1 리턴

7. 일치한다면 십자가의 갯수와 십자가 정보를 리턴해준다.

 

여기서 시간이 오래걸렸던 이유는

1) 십자가 크기 조건을 잘못 이해했음.

2) 십자가 크기를 먼저 서칭한 후, visit 에 표시할 것.

이 두 문제로 실패 시도를 많이했음...ㅠㅜㅜ

#include <iostream>
#include <vector>
using namespace std;
char map[101][101];
int n, m;
bool visit[101][101];
struct A
{
int x, y, s;	
};

int check(int y, int x) {
	int i=0;
	while(true) {
		i++;
		if(map[y-i][x] == '*' && map[y+i][x] == '*' 
			&& map[y][x+i] == '*' && map[y][x-i] == '*') {
			visit[y-i][x] = true;
			visit[y+i][x] = true;
			visit[y][x+i] = true;
			visit[y][x-i] = true;
		}

		else {
			i--;
			break;
		}
	}

	if(i != 0) {
		for(int j=0; j<i; j++) {
			visit[y-j][x] = true;
			visit[y+j][x] = true;
			visit[y][x-j] = true;
			visit[y][x+j] = true;
		}
		return i; 
	}
	return 0;
}

int main() {

	vector <A> v;
	scanf("%d %d", &n, &m);

	for(int i=0; i<n; i++)
			cin >> map[i];

	for(int i=0; i<n; i++) {
		for(int j=1; j<m-1; j++){
			if(map[i][j-1] == '*' && map[i][j] == '*'&& map[i][j+1] == '*'){
				int sizes = check(i, j);
				if(sizes > 0){
					A a;
					a.y = i+1;
					a.x = j+1;
					a.s = sizes;
					v.push_back(a);
				}
			}
		}
	}

	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++){
			if((visit[i][j] == true && map[i][j] == '.') ||(visit[i][j] == false && map[i][j] == '*')) {
				printf("-1\n");
				exit(0);
			}
		}



	printf("%lu\n", v.size());
	for(int i=0; i<v.size(); i++)
		printf("%d %d %d\n", v[i].y, v[i].x, v[i].s);
	return 0;
}