글 읽기 - BFS로 풀어보았는데, 문제가 틀린 이유를 잘 모르겠어요ㅠㅠ

r4you96 4년 전 0

질문이 많이 없긴 하지만

질문 란에 있는 반례들 전부 입력해서 해봤을땐 잘 나오는데

어째서인지 틀렸습니다만 자꾸 나오네요ㅠㅠ

18퍼센트까지 갔다가 틀렸습니다 나올때도 있어서

관련 질문 있길래 봤는데 이해가 잘 안가서요ㅠㅠ

도움주시면 감사하겠습니다.

#include<stdio.h>
typedef struct point {
	int x;
	int y;
}point;
char map[12][6];
int map_correct[12][6];
point queue[12 * 6 + 1];
point stack[12 * 6+1];
int max = 0;
int stack_top = -1;
int queue_top = -1;
int queue_bottom = -1;
int length = 0;
void stack_clear();
void stack_push(int y, int x);
point stack_pop();
void queue_clear();
void queue_push(int y, int x);
point queue_pop();
void puyo(int count);
void bfs(char color, int y, int x);
int main(void) {
	int i, j;
	char num;
	for (i = 0; i < 12; i++) {
		for (j = 0; j < 6; j++) {
			scanf("%c", &map[i][j]);
		}
		scanf("%c", &num);
	}
	puyo(0);

	printf("%d", max);

	return 0;
}
void stack_clear() {
	stack_top = -1;
	return;
}
void stack_push(int y, int x) {
	point p = { x,y };
	stack[++stack_top] = p;
	return;
}
point stack_pop() {
	return stack[stack_top--];
}
void queue_clear() {
	queue_top = -1;
	queue_bottom = -1;
}
void queue_push(int y, int x) {
	point p = { x,y };
	queue[++queue_top] = p;
	return;
}
point queue_pop() {
	return queue[++queue_bottom];
}
void puyo(int count) {
	int i, j, k;
	point tmp;
	int destroy = 0;
	if (count > max)
		max = count;

	//맵 방문 초기화
	for (i = 0; i < 12; i++) {
		for (j = 0; j < 6; j++) {
			map_correct[i][j] = 1;
		}
	}

	//맵에서 빈칸 아닌부분 찾기
	for (i = 0; i < 12; i++) {
		for (j = 0; j < 6; j++) {
			if (map[i][j] != '.' && map_correct[i][j] == 1){
				//bfs 시작 및 초기화
				length = 0;
				stack_clear();
				queue_clear();
				bfs(map[i][j], i, j);
				if (length > 3) { //4개 이상이었을 시 파괴
					destroy++;
					for (k = 0; k < length; k++) {
						tmp = stack_pop();
						map[tmp.y][tmp.x] = '.';
					}
				}
			}
		}
	}

	int bottoms;
	char tmp_color;
	for (i = 0; i < 6; i++) {
		bottoms = 0;
		//가장 밑에 있는 '.' 찾기
		for (k = 11; k >= 0; k--) {
			if (map[k][i] == '.') {
				bottoms = k;
				break;
			}
		}
		for (j = bottoms-1; j >= 0; j--) {
			if (map[j][i] != '.') {
				tmp_color = map[j][i];
				map[j][i] = '.';
				map[bottoms][i] = tmp_color;

				bottoms--;
				/*
				printf("\n");
				for (int l = 0; l < 12; l++) {
					printf("\n");
					for (int m = 0; m < 6; m++) {
						printf("%c", map[l][m]);
					}
				}*/
			}
		}
	}
	//한번 더 들어가기
	if (destroy > 0) {
		puyo(++count);
	}
	return;
}
void bfs(char color, int y, int x) {
	length++;
	map_correct[y][x] = -1;
	stack_push(y, x);
	//printf("BFS color : %c / x : %d / y : %d\n",color,x,y);
	int count = 0;
	point tmp;
	if (map[y + 1][x] == color && map_correct[y + 1][x] == 1) {
		queue_push(y + 1, x);
		count++;
	}
	if (map[y-1][x] == color && map_correct[y - 1][x] == 1) {
		queue_push(y-1, x);
		count++;
	}
	if (map[y][x+1] == color && map_correct[y][x + 1] == 1) {
		queue_push(y, x+1);
		count++;
	}
	if (map[y][x-1] == color && map_correct[y][x - 1] == 1) {
		queue_push(y, x - 1);
		count++;
	}

	for (int i = 0; i < count; i++) {
		tmp = queue_pop();
		bfs(color, tmp.y, tmp.x);
	}

	return;
}

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

문제

문제

출처

ICPC

BFS로 풀어보았는데, 문제가 틀린 이유를 잘 모르겠어요ㅠㅠ

r4you96 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말