글 읽기 - 반례좀 알려주세요 ㅠ

gustjs2080 4년 전 0

많은 반례들을 해보았는데 안됩니다.. ㅠㅠ

#include<stdio.h>
#include<stdlib.h>

typedef struct {
	int y;
	int x;
}Stack;
void BFS1(int size, int** input, int** visit);
void push(Stack* stack, int* top, int x, int y) {
	
	(*top)++;
	stack[(*top)].x = x;
	stack[(*top)].y = y;

}
void mergeSort(int*, int, int );
int pull(Stack* stack, int* top, int*x, int*y) {

	if (*top > -1) {
		*x = stack[(*top)].x;
		*y = stack[(*top)].y;
		(*top)--;
		return 1;
	}
	else
		return 0;

}

int main() {

	int size;
	int** input;
	int** visit;
	int* count;
	int max = 0;
	

	scanf("%d", &size);

	input = (int**)malloc(sizeof(int*)*size);
	for (int i = 0; i < size;i++) {
		input[i] = (int*)malloc(sizeof(int)*size);
		for (int j = 0; j < size; j++)
			scanf("%1d", &input[i][j]);
	}
	
	visit = (int**)malloc(sizeof(int*)*size);
	for (int i = 0; i < size;i++) {
		visit[i] = (int*)malloc(sizeof(int)*size);
		for (int j = 0; j < size; j++)
			visit[i][j] = 0;
	}
	
	

	BFS1(size, input, visit);

	



	for (int i = 0; i < size;i++)
		free(input[i]);
	free(input);

	for (int i = 0; i < size;i++)
		free(visit[i]);
	free(visit);
}
void BFS1(int size, int** input, int** visit) {
	Stack* stack;
	int top = -1;
	int num=0;
	int* count;

	stack = (Stack*)malloc(sizeof(Stack)*(size*size*size));
	
	count = (int*)malloc(sizeof(int)*size*size);
	for (int i = 0; i < size*size;i++)
		count[i] = 0;
	
	for (int i = 0;i < size;i++) {
		for (int j = 0;j < size;j++) {
			if (input[i][j] == 1 && visit[i][j] == 0) {
				int x = i;
				int y = j;
				do{
					
					if (top != -1)
						pull(stack, &top, &x, &y);
					else
						num++;

					if (visit[x][y] != 0)
						continue;
					else {
						visit[x][y] = num;
						count[num]++;
					}
					
					// 4방면 체크해서 stack에 집어넣는다.
				if (x != 0 && input[x - 1][y] == 1)
					push(stack, &top, x - 1, y);
				if (y != size - 1 && input[x][y + 1] == 1)
					push(stack, &top, x, y + 1);
				if (x != size - 1 && input[x + 1][y] == 1)
					push(stack, &top, x + 1, j);
				if (y != 0 && input[x][y - 1] == 1)
					push(stack, &top, x, y - 1);
				} while (top != -1);

			}
		}
	}

	printf("%d", num);
	
	
	if (num != 0) {
		mergeSort(count, 1, num);  // mergeSort
		for (int i = 1;i <= num;i++) {
			printf("\n");
			printf("%d", count[i]);
	    }
	}

	free(count);
	free(stack);
	
}
void mergeSort(int* count, int start, int end) {

	int mid = (start + end) / 2;
	int* temp;
	int num = 0;
	int i;
	int j;

	// 뜨래쉬홀드
	if (start == end)
		return;

	
	
	mergeSort(count, start, mid);
	mergeSort(count, mid+1, end);

	temp = (int*)malloc(sizeof(int)*(end - start + 1));

	i = start;
	j = mid+1;
	while (!(i==mid+1&&j==end+1)) {
		
		if (i == mid+1)
			temp[num++] = count[j++];
		else if (j == end+1)
			temp[num++] = count[i++];
		else {
			if(count[i]<count[j])
				temp[num++] = count[i++];
			else
				temp[num++] = count[j++];
		}
	}
	num = 0;
	for (int k = start;k <= end;k++) {
		count[k] = temp[num++];
	}


	free(temp);
}

djm03178 4년 전 0

코드가 긴데 설명이 없어서 무슨 로직인지 이해는 못 하겠지만, 눈에 띄는 건 BFS인데 스택을 썼군요. BFS는 무조건 큐로 하는 자료구조입니다.

jh05013 4년 전 0

5
11011
11111
00110
11011
11011

jh05013 4년 전 0

그리고 https://www.acmicpc.net/proble...

alssel2525 4년 전 0

1번 입력처럼 생긴 4개짜리 단지는 이상하게 세는군요.

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

문제

문제

출처

ICPC

반례좀 알려주세요 ㅠ

gustjs2080 4년 전 0

djm03178 4년 전 0

jh05013 4년 전 0

jh05013 4년 전 0

alssel2525 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말