글 읽기 - 반례나 틀린 점을 찾고 싶습니다!

meumang 4년 전 0

현 질문 계시판에 있는 관련 질문들의 값들을 넣어봐도 다 맞다고 하는데 어디가 틀렸는지 잘 모르겠습니다 ㅜㅜ

코드의 작동 방법은

draw()부분에서 전역으로 설정된 square배열을 색칠해진 부분과 색칠해지 않는 부분으로 나누고

refind()부분에서 색이 칠해지지 않은 부분. 즉 bfs를 시작할 부분을 찾고

bfs() 함수에서 시작점 기준으로 bfs를 돌립니다.

각 영역의 넓이는 csum으로,

나누어지는 부분의 개수는 size로 측정합니다.

visited 배열은 나누어지는 부분에 따른 각 영역의 넓이를 저장해 주는 배열 역할을 합니다.

답변해 주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
char arr[101][5];
int square[101][101];
int sum;
int csum;

typedef struct quu {
	int x;
	int y;
}quu;
int visited[10001];
queue<quu>q;

void draw(int K) {
	for (int i = 0; i < K; i++) {
		int st_x = arr[i][0] - '0';
		int st_y = arr[i][1] - '0';
		int en_x = arr[i][2] - '0';
		int en_y = arr[i][3] - '0';

		for (int j = st_y; j < en_y; j++) {
			for (int k = st_x; k < en_x; k++) {
				if (square[j][k] == 0) {
					square[j][k] = 1;
					sum++;
				}
			}
		}
	}
}

int refind(int N, int M) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (square[i][j] == 0) {
				q.push({ j,i });
				return 1;
			}
		}
	}
	return 0;
}

int bfs(int N, int M) {
	int remain = M * N - sum;
	int size = 0;
	while (remain > 0) {
		refind(N, M);
		square[q.front().y][q.front().x] = 1;
		while (!q.empty()) {
			quu here = q.front();
			q.pop();
			csum++;
			remain--;
			if (square[here.y + 1][here.x] == 0 && here.y + 1 < N) {
				q.push({ here.x, here.y + 1 });
				square[here.y + 1][here.x] = 1;
			}
			if (square[here.y][here.x + 1] == 0 && here.x + 1 < M) {
				q.push({ here.x + 1, here.y });
				square[here.y][here.x + 1] = 1;
			}
			if (square[here.y][here.x - 1] == 0 && here.x - 1 >= 0) {
				q.push({ here.x - 1, here.y });
				square[here.y][here.x - 1] = 1;
			}
			if (square[here.y - 1][here.x] == 0 && here.y - 1 >= 0) {
				q.push({ here.x, here.y - 1 });
				square[here.y - 1][here.x] = 1;
			}
		}
		visited[size] = csum;
		csum = 0;
		size++;
	}
	return size;
}

int main(void) {
	int M, N, K;
	//N: 행
	//M:열
	cin >> N >> M >> K;
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> arr[i][j];
		}
	}

	draw(K);//draw the table
	int size = bfs(N, M);
	sort(visited, visited + size);
	cout << size << "\n";
	for (int i = 0; i < size; i++)
		cout << visited[i] << " ";
	return 0;

}

meumang 4년 전 0

입력 값을 처음에 char형으로 받아서 두자리 수 이상의 좌표 값에 에러가 났던 거였습니다...이럴수가ㅠㅠㅠ

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

문제

문제

출처

ICPC

반례나 틀린 점을 찾고 싶습니다!

meumang 4년 전 0

meumang 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말