글 읽기 - 게시판 반례를 다 확인 해도 더이상의 반례를 못찾겠습니다 ㅠㅠ

cpdim001 5년 전 0

게시판의 반례를 모두 확인하고, 로컬에서는 정답을 내고 있습니다만,

더이상의 반례를 못찾겠습니다.. 항상 이부분이 걸리는거 같아 Queue 값을 충분히 주었는데도 "틀렸습니다" 가 나오네요.

고수님들 조언을 부탁 드립니다. ㅠㅠ

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

int Box[27][27]; int Visited[27][27]; Queue[9000000]; int H_cnt[500];
int Queue_cnt, Qx, Qy, rear, front, H, N, Sx, Sy, cnt;

void Q_Init() {
	for (int i = 0; i < 9000000; i++) { Queue[i] = 0; Queue_cnt = 0; rear = 0; front = 0; Qx = 0; Qy = 0; }
}
int isEmpty() {
	if (rear == front) { return 1; }
	else { return 0; }
}
void push(int a, int b) {
	if (rear < 9000000) {
		Queue[rear++] = a; Queue[rear++] = b; Queue_cnt++;
	}
}
void pop() {
	if (!isEmpty()) {
		Qx = Queue[front++]; Qy = Queue[front++]; Queue_cnt--;
	}
}
void Start_Point() {//Box를 돌면서 최초로 만나는 1을 Start_Point로 해서 Sx, Sy 값을 설정하는 함수
	int flag = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (Box[i][j] == 1 && flag == 0) { Sx = i; Sy = j; flag = 1; }
		}
	}
}
int bfs(int a, int b) {
	push(a, b); int House = 0;
	while (!isEmpty()) {
		pop(); a = Qx; b = Qy; 
		if (Box[a][b] != 0) {//pop 해 준 항목은 0으로 함.
			House++; H--; Box[a][b] = 0;
		}
		//if(상하좌우에 1이 있고, 방문한 기록이 없으면, 
        //--> 해당 셀의 주소를 큐에 push 하고, 방문한 기록을 남기고, cnt++ 해 준다)
		if (Box[a + 1][b] == 1 && Visited[a + 1][b] != 1) { push(a + 1, b); Visited[a + 1][b]; }
		if (Box[a - 1][b] == 1 && Visited[a - 1][b] != 1) { push(a - 1, b); Visited[a - 1][b]; }
		if (Box[a][b + 1] == 1 && Visited[a][b + 1] != 1) { push(a, b + 1); Visited[a][b + 1]; }
		if (Box[a][b - 1] == 1 && Visited[a][b - 1] != 1) { push(a, b - 1); Visited[a][b - 1]; }
	}
	return House;
}
void swap(int a, int b) {
	int tmp = a; a = b; b = tmp;
}
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) { //0 번째 행과 0번째 열은 모두 0으로 해 준다.
		for (int j = 1; j <= N; j++) {
			scanf("%1d", &Box[i][j]);
			if (Box[i][j] == 1) { H++; } //집의 총 개수 H를 카운트 해 준다
		}
	}
    // H : 집의 개수. 집의 개수가 0이 될때 까지 돌린다 (집의 개수는 방문 할때마다 H-- 해 준다)
	while (H) {  
		Start_Point(); //최초로 만나는 1을 Start_Point로 해서 Sx, Sy 값을 설정하는 함수
        //단지 0, 1, 2번의 집의 개수 :  H_cnt[0], H_cnt[1], H_cnt[2] ...
		H_cnt[cnt++] = bfs(Sx, Sy); 
	}
	//H_cnt[] 배열의 각 요소를 오름차순으로 정렬
	for (int k = 0; k < cnt; k++) { //단지 개수만큼 돌린다
		for (int i = 0; i < cnt; i++) {
			if (H_cnt[i] > H_cnt[i + 1]) { swap(H_cnt[i], H_cnt[i + 1]); }
		}
	}
	printf("%d", cnt); //단지 개수 출력
	for (int i = 0; i < cnt; i++) { // 단지 별 가장 작은 수 부터 출력
		printf("\n%d", H_cnt[i]);
	}
}

djm03178 5년 전 0

40번째 줄에서 "방문한 기록을 남기고, cnt++ 해 준다"라고 했는데 기록을 남기고 있지 않습니다.

Visited[a + 1][b]; 는 아무런 의미가 없는 문장입니다.

jaehoo1 5년 전 0

https://ideone.com/dYrMDr

0 출력해야 합니다

cpdim001 5년 전 0

@djm03178 님

답변 감사합니다. cnt++ 는 63번째 줄에 넣어서 구현 했었습니다. 코멘트를 수정했어야 하는데 급한 마음에 그낭 올렸네요. 아래에 다시 올려봅니다.

@jaehoo1 님

주신 반례를 적용했는데, 결과가 0으로 나오네요.

그런데 여전히 코드를 넣으면 "틀렸습니다" 가 나옵니다 ㅠㅠ

큐 값도 쓸수 있는 최대치를 넣어 돌렸는데도 안되는데 대체 뭐가 잘못된걸까요...

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

int Box[27][27]; int Visited[27][27]; Queue[9990000]; int H_cnt[500];
int Queue_cnt, Qx, Qy, rear, front, H, N, Sx, Sy, cnt;

void Q_Init() {
	for (int i = 0; i < 9990000; i++) { Queue[i] = 0; Queue_cnt = 0; rear = 0; front = 0; Qx = 0; Qy = 0; }
}
int isEmpty() {
	if (rear == front) { return 1; }
	else { return 0; }
}
void push(int a, int b) {
	if (rear < 9990000) {
		Queue[rear++] = a; Queue[rear++] = b; Queue_cnt++;
	}
}
void pop() {
	if (!isEmpty()) {
		Qx = Queue[front++]; Qy = Queue[front++]; Queue_cnt--;
	}
}
void Start_Point() {//Box를 돌면서 최초로 만나는 1을 Start_Point로 해서 Sx, Sy 값을 설정하는 함수
	int flag = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (Box[i][j] == 1 && flag == 0) { Sx = i; Sy = j; flag = 1; }
		}
	}
}
int bfs(int a, int b) {
	push(a, b); int House = 0;
	while (!isEmpty()) {
		pop(); a = Qx; b = Qy; 
		if (Box[a][b] != 0) {//pop 해 준 항목은 0으로 함.
            // 해당 Box값을 0으로 해 주고, 총 집의 개수(H)에서 방문한 집을 --, 해당 단지내의 집의 수를 ++한다
			House++; H--; Box[a][b] = 0;
		}
		//if(상하좌우에 1이 있고, 방문한 기록이 없으면, --> 해당 셀의 주소를 큐에 push 하고, 방문한 기록을 남긴다)
		if (Box[a + 1][b] == 1 && Visited[a + 1][b] != 1) { push(a + 1, b); Visited[a + 1][b]; }
		if (Box[a - 1][b] == 1 && Visited[a - 1][b] != 1) { push(a - 1, b); Visited[a - 1][b]; }
		if (Box[a][b + 1] == 1 && Visited[a][b + 1] != 1) { push(a, b + 1); Visited[a][b + 1]; }
		if (Box[a][b - 1] == 1 && Visited[a][b - 1] != 1) { push(a, b - 1); Visited[a][b - 1]; }
	}
	return House;
}
void swap(int a, int b) {
	int tmp = a; a = b; b = tmp;
}
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) { 
		for (int j = 1; j <= N; j++) {
			scanf("%1d", &Box[i][j]);
			if (Box[i][j] == 1) { H++; } //집의 총 개수 H를 카운트 해 준다
		}
	}
	while (H) {  // H : 집의 개수. 집의 개수가 0이 될때 까지 돌린다 (집의 개수는 방문 할때마다 H-- 해 준다)
		Start_Point(); //최초로 만나는 1을 Start_Point로 해서 Sx, Sy 값을 설정하는 함수
		H_cnt[cnt++] = bfs(Sx, Sy); //단지 0, 1, 2번의 집의 개수 :  H_cnt[0], H_cnt[1], H_cnt[2] ...
	}
	//H_cnt[] 배열의 각 요소를 오름차순으로 정렬
	for (int k = 0; k < cnt; k++) { //단지 개수만큼 돌린다
		for (int i = 0; i < cnt; i++) {
			if (H_cnt[i] > H_cnt[i + 1]) { swap(H_cnt[i], H_cnt[i + 1]); }
		}
	}
	printf("%d", cnt); //단지 개수 출력
	for (int i = 0; i < cnt; i++) { // 단지 별 가장 작은 수 부터 출력
		printf("\n%d", H_cnt[i]);
	}
}