글 읽기 - 반례 부탁드립니다.

kyle1024 4년 전 0

게시판에 등록된 반례들을 확인하였는데 잘 동작되는데,

채점할 땐 바로 틀렸다고 나오네요.

반례 부탁드립니다.

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

int N, m[25][25];
bool check[25][25];
int movedx[] = { -1, 0, 0, 1 };
int movedy[] = { 0, 1, -1, 0 };
int mensionSize[25]; //단지내 집 수 저장 배열

void bfs(int y, int x, int Num) {
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));
	check[y][x] = true;
	mensionSize[Num] += 1;
	while (!q.empty()) {
		int currX = q.front().second;
		int currY = q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nextX = min(N - 1, max(0, currX + movedx[i])); // 0~N-1 제한
			int nextY = min(N - 1, max(0, currY + movedy[i])); // 0~N-1 제한
			if (m[nextY][nextX] == 1 && check[nextY][nextX] == false) {
				q.push(make_pair(nextY, nextX));
				check[nextY][nextX] = true;
				mensionSize[Num] += 1;
			}
		}
	}
}

int main() {

    //데이터 입력
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &m[i][j]);
		}
	}	
	
    //카운트를 0부터 시작
	int Num = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (m[i][j] == 1 && check[i][j] == false) {
				//BFS
				bfs(i, j, Num);
				Num += 1; //케이스 끝날 때 +1 됨
			}
		}
	}

	printf("%d\n", Num);
	sort(mensionSize, mensionSize + Num);
	for (int i = 0; i < Num; i++) { printf("%d\n", mensionSize[i]); }

	return 0;
}

kangsm02 4년 전 1

단지 수가 25를 넘어가면..?

kyle1024 4년 전 0

아.. 단지 수 배열 크기를 키우니까 해결되었습니다.

감사합니다!

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

문제

문제

출처

ICPC

반례 부탁드립니다.

kyle1024 4년 전 0

kangsm02 4년 전 1

kyle1024 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말