글 읽기 - [C] 2667 반례 부탁드립니다.

iwbabpa 2년 전 0

검색해서 나오는 모든 반례 찾아서 넣어봤지만 틀렸습니다로 계속 나오네요.

아래 코드에 대한 수정사항 or 반례 부탁드리겠습니다.

도움 요청합니다.

#include <stdio.h>

#define max 26
//#define DEBUG
//#define DEBUG2

int arr_home[max][max] = { 0, };
int num;
int que[max*max/2] = { 0, };
int que_cnt = 0;

int bfs_que[max*max][2] = { 0, };
int bfs_que_cnt = 0;


void bfs_push(int x, int y){
#ifdef DEBUG
	printf("bfs_push -  x : %d / y : %d / bfs_que_cnt : %d / que_cnt : %d \n", x, y, bfs_que_cnt, que_cnt);
#endif

	bfs_que[bfs_que_cnt][0] = x;
	bfs_que[bfs_que_cnt][1] = y;
	bfs_que_cnt++;

}

void bfs_pop(int *x, int *y){
	bfs_que_cnt--;
	*x = bfs_que[0][0];
	*y = bfs_que[0][1];
#ifdef DEBUG
	printf("bfs_pop -  x : %d / y : %d \n", *x, *y);
#endif
	if (bfs_que_cnt > 0){
		for (int i = 0; i < bfs_que_cnt; i++){
			bfs_que[i][0] = bfs_que[i + 1][0];
			bfs_que[i][1] = bfs_que[i + 1][1];
		}
	}
}

int search_home(int x, int y){
	//if (x > max || y > max) return;
#ifdef DEBUG
	printf("Search_home present : x : %d y : %d \n", x, y);
#endif
	int flag = 0;	
	if (arr_home[x + 1][y] && x + 1 <= num) {
#ifdef DEBUG
		printf("Search_home right \n");
#endif
		arr_home[x + 1][y] = 0; 
		bfs_push(x + 1, y);
		que[que_cnt] = que[que_cnt] + 1;
		flag = 1;
	} // right
	if (arr_home[x][y + 1] && y + 1  <= num) {
#ifdef DEBUG
		printf("Search_home down \n");
#endif
		arr_home[x][y + 1] = 0;
		bfs_push(x, y + 1);
		que[que_cnt] = que[que_cnt] + 1;
	
		flag = 1;
	} // down
	if (arr_home[x - 1][y] && x - 1  > 0) {
#ifdef DEBUG
		printf("Search_home left \n");
#endif
		arr_home[x - 1][y] = 0;
		bfs_push(x - 1, y);
		que[que_cnt] = que[que_cnt] + 1;
		flag = 1;
	} // left
	if (arr_home[x][y - 1] && y - 1 > 0) {
#ifdef DEBUG
		printf("Search_home up \n");
#endif
		arr_home[x][y - 1] = 0;
		bfs_push(x, y - 1);
		que[que_cnt] = que[que_cnt] + 1;
		flag = 1;
	} // up
	if (flag == 0) return 1;
	else           return 0;
}

void sort_que(){
	for (int i = 0; i < max - 1; i++){
		for (int j = i + 1; j <= max; j++){
			if (que[i] > que[j] && que[i] != 0 && que[j] != 0){
				int temp;
				temp = que[i];
				que[i] = que[j];
				que[j] = temp;
			}
		}
	}
}

int main(){

#ifdef DEBUG2
	freopen("input.txt", "r", stdin);
#endif
	int no_home, i_b, j_b;
	scanf("%d", &num);
#ifdef DEBUG
	printf("Num : %d\n", num);
#endif

	for (int i = 1; i <= num; i++){
		for (int j = 1; j <= num; j++){
			scanf("%1d", &arr_home[j][i]);
		}
	}
#ifdef DEBUG
	for (int i = 1; i <= num; i++){
		for (int j = 1; j <= num; j++){
		    printf("%d", arr_home[j][i]);
		}
		printf("\n");
	}
#endif


	for (int i = 1; i <= num; i++){
		for (int j = 1; j <= num; j++){
			if (arr_home[j][i] == 1){
				bfs_push(j, i);
				arr_home[j][i] = 0;
				que[que_cnt] = que[que_cnt] + 1;
				i_b = i;
				j_b = j;
				while (1){
					bfs_pop(&j_b, &i_b);
					no_home = search_home(j_b, i_b);
#ifdef DEBUG
					printf("before que[%d] : %d / no_home : %d  / bfs_que_cnt : %d \n", que_cnt, que[que_cnt], no_home , bfs_que_cnt);
#endif
					if (bfs_que_cnt == 0 && no_home){
#ifdef DEBUG
						printf("break que[%d] : %d \n", que_cnt, que[que_cnt]);
#endif

						que_cnt++;
#ifdef DEBUG
						printf("que_cnt : %d / i : %d / j : %d  \n", que_cnt, i_b, j_b);
#endif
						break;
					}
				}
			}
		}
	}

	sort_que();

	printf("%d\n", que_cnt);
	for (int k = 0; k < que_cnt; k++){
		
		if (k == que_cnt - 1){
#ifdef DEBUG
			printf("K : %d / que : ",k);
#endif
			printf("%d", que[k]);
		}
		else {
#ifdef DEBUG
			printf("K : %d / que : ", k);
#endif
			printf("%d\n", que[k]);
		}
	}

	return 0;
}

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

문제

문제

출처

ICPC

[C] 2667 반례 부탁드립니다.

iwbabpa 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말