# Bitmap

# 문제

 

# 입력 및 출력

 

# 풀이

처음엔 재귀를 돌 때 size로 돌게 했었다.

근데 시간초과가 뜨길래 조건문을 걸어서 필요한 부분만 보면 되나 했지만

출력을 위해선 전부 돌아야 하기 때문에 문제가 없어 보였다.

 

그래서 일단 재귀함수의 파라미터를 size가 아닌 인덱스 값으로 주고

start x, start y, end x, end y 값을 사용해서 돌도록 했다.

 

 

해당 문제가 백준에도 있어서 백준에서 먼저 문제를 풀었다.

근데 백준에서는 맞는 답이 espa에서 돌리니까 시간 초과가 떴다.

그래서 fstream 관련해서 시간 초과 문제가 있는지 찾아봤다.

 

중요한 점
fstream을 사용했는데 해당 파일 입출력 라이브러리가 cstdio 라이브러리의 파일 입출력보다 시간이 매우 많이 걸린다.
그래서 fstream 대신 fopen을 사용해서 파일 입출력을 했다.
이렇게 되니까 string으로 입출력이 불가능해서 char형으로 하나씩 받아줘야했다.
그래서 코드가 매우 복잡해짐. 

파일 입출력 시간 관련 블로그를 참고하면 좋을 것 같다.

https://nidelva.tistory.com/13

C++) ifstream 읽기 성능 비교

주의할 점
char형으로 하나씩 fscanf 할때 개행문자인 \n도 따로 확인해줘야 함.
입력이 길 때 50자 이상이 되면 개행문자가 하나 나오기 때문에 count를 해서 확인해줘야 함.
그리고 fscanf로 읽을 때 해당 케이스의 입력이 끝났는지 확인하기 위해
다음 케이스의 format을 읽게 되는 경우가 있어서 이 경우도 확인해서 format을 저장해야한다.

 

fstream을 사용했을 때

 

#pragma warning(disable:4996)
#include <cstdio>
#include <string>
using namespace std;

FILE* fcin = fopen("bitmap.inp", "r");
FILE* fcout = fopen("bitmap.out", "w");

char bitmap[200][200];
int N, M, index, cnt;
string dstr;

void btod(int sx, int sy, int ex, int ey) {
	bool zero, one;
	zero = one = true;
	for (int i = sx; i <= ex; i++) {
		for (int j = sy; j <= ey; j++) {
			if (bitmap[i][j] == '1') zero = false;
			if (bitmap[i][j] == '0') one = false;
		}
	}
	if (cnt >= 50) { fprintf(fcout, "\n"); cnt = 0; }
	cnt++;
	if (zero == true) { fprintf(fcout, "0"); }
	else if (one == true) { fprintf(fcout, "1"); }
	else {
		fprintf(fcout, "D");
		int xmid = (sx + ex + 1) / 2 + (ex - sx + 1) % 2;
		int ymid = (sy + ey + 1) / 2 + (ey - sy + 1) % 2;
		if (xmid - 1 <= ex && ymid - 1 <= ey) btod(sx, sy, xmid - 1, ymid - 1);
		if (xmid - 1 <= ex && ymid <= ey) btod(sx, ymid, xmid - 1, ey);
		if (xmid <= ex && ymid - 1 <= ey) btod(xmid, sy, ex, ymid - 1);
		if (xmid <= ex && ymid <= ey) btod(xmid, ymid, ex, ey);
	}
}

void dtob(int sx, int sy, int ex, int ey) {
	char c = dstr[index];
	index++;
	if (c == 'D') {
		int xmid = (sx + ex + 1) / 2 + (ex - sx + 1) % 2;
		int ymid = (sy + ey + 1) / 2 + (ey - sy + 1) % 2;
		if (xmid - 1 <= ex && ymid - 1 <= ey) dtob(sx, sy, xmid - 1, ymid - 1);
		if (xmid - 1 <= ex && ymid <= ey) dtob(sx, ymid, xmid - 1, ey);
		if (xmid <= ex && ymid - 1 <= ey) dtob(xmid, sy, ex, ymid - 1);
		if (xmid <= ex && ymid <= ey) dtob(xmid, ymid, ex, ey);
	}
	else {
		for (int i = sx; i <= ex; i++) {
			for (int j = sy; j <= ey; j++) {
				bitmap[i][j] = c;
			}
		}
		return;
	}
}

void input_btype() {
	int check = 0, count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (count >= 50) {
				check = 1;
				count = 0;
				fscanf(fcin, "\n");
			}
			count++, check = 0;
			fscanf(fcin, "%c", &bitmap[i][j]);
		}
	}
	if (check != 1) fscanf(fcin, "\n");
	fprintf(fcout, "D%4d%4d\n", N, M);
}

char input_dtype() {
	char f;
	while (true) {
		fscanf(fcin, "%c", &f);
		if (f == '\n') continue;
		else if (f == '0' || f == '1' || f == 'D') {
			dstr += f;
		}
		else break;
	}
	fprintf(fcout, "B%4d%4d\n", N, M);
	return f;
}

void print_btype() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (cnt >= 50) {
				fprintf(fcout, "\n");
				cnt = 0;
			}
			fprintf(fcout, "%c", bitmap[i][j]);
			cnt++;
		}
	}
}

int main() {
	char format;
	int check = 0;
	while (true) {
		cnt = 0, index = 0, dstr = "";
		if (check == 0) {
			fscanf(fcin, "%c", &format);
		}
		if (format == '#') break;
		fscanf(fcin, "%d %d\n", &N, &M);
		if (format == 'B') {
			check = 0;
			input_btype();
			btod(0, 0, N - 1, M - 1);
		}
		else {
			check = 1;
			format = input_dtype();
			dtob(0, 0, N - 1, M - 1);
			print_btype();
		}
		fprintf(fcout, "\n");
	}
}

 

해결^~^