글 읽기 - 색종이 붙이기 전처리(?)하는 방식으로 풀었는데 (코드설명있습니당)

shinyou1024 4년 전 0

DFS기는 한데 실행 전에

1인 칸마다 pre()함수를 돌려서 해당 칸을 첫 칸으로 하면 몇짜리 정사각형을 만들 수 있는지 rec배열에 기록해줬습니다.

예를 들어, 입력 일부분이

1 1 1 0 0

1 1 1 1 1

0 0 1 1 1

이렇다면 rec배열에는

2 2 1 0 0

1 1 3 2 1

0 0 2 2 1

0 0 1 1 1 이렇게 저장됩니다.

테스트 케이스는 다 나와서 어떻게 디버깅할지 막막하네용...

의견 부탁드립니다!

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

struct Pos {
	int y, x;
	Pos(int y, int x) :y(y), x(x) {};
};
int map[10][10];
int rec[10][10]; // i, j를 시작점으로 만들 수 있는 가장 큰 정사각형
int tmp[10][10];
int total;
vector<Pos> cell;
int ans = 100;
int pre(int y, int x) {
	// 5확인
	int flag = 1;
	for (int i = 0; i < 5; i++) {
		int ny = y + i;
		for (int j = 0; j < 5; j++) {
			int nx = x + j;
			if (map[ny][nx] == 0 || ny<0 || ny>9 || nx<0||nx>9) {
				flag = 0;
				break;
			}
		}
	}
	if (flag) return 5;
	flag = 1;

	// 4확인
	for (int i = 0; i < 4; i++) {
		int ny = y + i;
		for (int j = 0; j < 4; j++) {
			int nx = x + j;
			if (map[ny][nx] == 0 || ny < 0 || ny>9 || nx < 0 || nx>9) {
				flag = 0;
				break;
			}
		}
	}
	if (flag) return 4;
	flag = 1;

	// 3확인
	for (int i = 0; i < 3; i++) {
		int ny = y + i;
		for (int j = 0; j < 3; j++) {
			int nx = x + j;
			if (map[ny][nx] == 0 || ny < 0 || ny>9 || nx < 0 || nx>9) {
				flag = 0;
				break;
			}
		}
	}
	if (flag) return 3;
	flag = 1;

	// 2확인
	for (int i = 0; i < 2; i++) {
		int ny = y + i;
		for (int j = 0; j < 2; j++) {
			int nx = x + j;
			if (map[ny][nx] == 0 || ny < 0 || ny>9 || nx < 0 || nx>9) {
				flag = 0;
				break;
			}
		}
	}
	if (flag) return 2;
	else return 1;

}

void visit_check(int y, int x, int k) {
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++)
			tmp[i][j] = 1;
	}
}

// (y, x)를 덮는다
void dfs(int idx, int cnt, int five, int four, int three, int two, int one, int visit[10][10], int paper) {
	if (paper > ans) return; // 컷팅

	// 다 덮은 경우
	if (cnt == cell.size()) {
		if (paper < ans) {
			ans = paper;
		}
		return;
	}
	
	int y = cell[idx].y; int x = cell[idx].x;

	if (visit[y][x]) dfs(idx + 1, cnt, five, four, three, two, one, visit, paper); // 이미 덮였음

	memcpy(tmp, visit, sizeof(tmp));
	if (rec[y][x] == 5 && five>0) {
		visit_check(y, x, 5);
		dfs(idx + 1, cnt + 25, five - 1, four, three, two, one, tmp, paper+1);
	}
	if (rec[y][x] >=4 && four>0) {
		visit_check(y, x, 4);
		dfs(idx + 1, cnt + 16, five, four-1, three, two, one, tmp, paper+1);
	}
	if (rec[y][x] >= 3 && three>0) {
		visit_check(y, x, 3);
		dfs(idx + 1, cnt + 9, five, four, three - 1, two, one, tmp, paper+1);
	}
	if (rec[y][x] >= 2 && two>0) {
		visit_check(y, x, 2);
		dfs(idx + 1, cnt + 4, five, four, three, two - 1, one, tmp, paper+1);
	}

	// 1로 덮는 경우
	if (one > 0) {
		visit_check(y, x, 1);
		dfs(idx + 1, cnt + 1, five, four, three, two, one - 1, tmp, paper + 1);
	}
}
int main() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> map[i][j];
			if(map[i][j])
			cell.push_back(Pos(i, j));
		}
	}

	// 전처리
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map[i][j]==1) {
				int k = pre(i, j);
				rec[i][j] = k;
			}
		}
	}
	
	dfs(0, 0, 5, 5, 5, 5, 5, tmp, 0);
	
	if (ans == 100) cout << -1;
	else cout << ans;
	return 0;
}

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

문제

문제

출처

ICPC

색종이 붙이기 전처리(?)하는 방식으로 풀었는데 (코드설명있습니당)

shinyou1024 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말