글 읽기 - 반례 혹은 소스 한 번 확인 부탁드립니다.

choijunsu 3년 전 0

혹시 몰라 주석을 추가 했습니다. 다른 분들이 올려주신 반례 찾아서 해봤지만 결과는 잘 나오고 혼자서 틀릴만한 테스트 케이스를 만들어 봐도 결과는 잘 나오는데 18퍼센트에서 틀리네요

소스에서 먼저 큐(loc, que)와 visit을 사용하여 loc는 BFS 탐색으로 쓰이고 que는 visit과 함께 중복되지 않도록 뿌요 좌표를 저장하는 용도로 사용합니다.

메인에서 BFS를 호출하여 탐색이 끝나면 que의 사이즈가 4이상 미만일 경우로 나누어 이상일 경우 뿌요를 x로 표시 후 큐를 비우고 미만일 경우 뿌요가

만들어지지 않기에 그냥 que를비웁니다. 이때 que 는 visit을 참고하여 데이터를 추가하기에 중복된 좌표 값은 없습니다.

끝나면 다시 메인으로 돌아와 계속해서 뿌요가 있는지 탐색을 계속 진행합니다. 2중 for문이 끝나면 모든 좌표 탐색 첫 번째 사이클이 끝나며 change()함수로 넘어가 표시된 x(뿌요)를 지우는 동작을 수행합니다. 수행 후 계속해서 뿌요가 없을때 까지 반복하는 로직입니다.

정리를 하자면

1.메인에서 색깔로 저장된 데이터마다 BFS를 호출하여 뿌요를 탐색.

2. 탐색된 뿌요의 사이즈에 따라 x표시 여부 결정 ->

3. 한 사이클(12,6 사이즈)가 끝나면 change() 함수 호출하여 x표시 된 뿌요 삭제 -> 해당 사이클이 끝날 때까지 뿌요가 없으면 종료

반례 외에 혹시 소스가 잘 못 되었는지 몰라서 소스도 한 번 검토 부탁드립니다. 잘 안풀리네요,,

#include <iostream>
#include <queue>
using namespace std;
char puyo[12][6];
int visit[12][6] = { {0,} };
int visit_Backup[12][6] = { {0, } };
int arw[2] = { -1,1 };
int counting = 0;
bool flag = 0;
queue <pair <int, int>> loc, que;
char ch[12];

void change() { // 뿌요 삭제 수행 함수
	counting++; // change가 실행되면 뿌요가 있다는 뜻으로 1회 추가
	for (int j = 0; j < 6; j++) {
		for (int i = 0; i < 12; i++) {
			if (puyo[i][j] == 'x') {
				ch[0] = '.';
				for (int x = 1; x <= i; x++) {
					ch[x] = puyo[x - 1][j];
				}
				for (int x = 0; x <= i; x++) {
					puyo[x][j] = ch[x];
				}
			}
		}
	}

}
void BFS(char color) { 

	int num = 1;

	while (loc.size() != 0) {
		int first = loc.front().first;
		int second = loc.front().second;
		loc.pop();
		for (int i = 0; i < 2; i++) {
			if (puyo[first + arw[i]][second] == color && first + arw[i] > -1 && first + arw[i] < 12 && !visit[first + arw[i]][second]) {
				visit[first + arw[i]][second] = 1;
				loc.push(make_pair(first + arw[i], second)); //BFS탐색 큐
				que.push(make_pair(first + arw[i], second)); //뿌요 위치 저장
			}
			if (puyo[first][second + arw[i]] == color && second + arw[i] > -1 && second + arw[i] < 12 && !visit[first][second + arw[i]]) {
				visit[first][second + arw[i]] = 1;
				loc.push(make_pair(first, second + arw[i]));
				que.push(make_pair(first, second + arw[i]));
			}
		}
	}
	if (que.size() < 4) //4미만일 경우 저장된 뿌요 위치 삭제 및 visit 원복
		while (que.size() != 0) {
			visit[que.front().first][que.front().second] = 0;
			que.pop();
		}
	else { //4이상일 경우 저장된 뿌요 위치를 x로 표시
		flag = 0;
		while (que.size() != 0) {
			puyo[que.front().first][que.front().second] = 'x';
			que.pop();
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i < 12; i++)
		for (int j = 0; j < 6; j++) {
			cin >> puyo[i][j];
		}

	while (!flag) {
		flag = 1;
		for (int i = 11; i > -1; i--) { //뿌요 탐색 for문이 종료가 한 싸이클
			for (int j = 0; j < 6; j++) {
				if (puyo[i][j] != '.' && puyo[i][j] != 'x') { //색깔 일 때 BFS호출
					visit[i][j] = 1;
					loc.push(make_pair(i, j));
					que.push(make_pair(i, j));
					BFS(puyo[i][j]);
				}
			}
		}
		for (int i = 0; i < 12; i++) //visit 초기화
			for (int j = 0; j < 6; j++) visit[i][j] = visit_Backup[i][j];

		if (!flag)change();
	}

	cout << counting;
}

댓글을 작성하려면 로그인해야 합니다.