글 읽기 - 색종이 붙이기 질문입니다.

zhh1020 4년 전 0

DFS를 이용해서 풀려고 했습니다.

색종이의 갯수와 범위가 벗어나지 않으면 DFS를 통해 붙여주고 ( map[y][x] = 2 ) 붙인 색종이의 크기만큼을 제외시켰습니다.

어디 부분이 틀렸는지 모르겠습니다..

#include <iostream>
using namespace std;
int map[11][11];
int paper[6];
int ans = 0;
bool pass;
bool inside(int y, int x) {
	return y >= 1 && y <= 10 && x >= 1 && x <= 10;
}

bool is_print(int y, int x, int SIZE) {

	for (int dy = y; dy < y + SIZE; dy++) {
		for (int dx = x; dx < x + SIZE; dx++) {
			if (map[dy][dx] != 1 || !inside(dy,dx))
				return false;
		}
	}
	return true;
}

void print(int y, int x, int SIZE, int color) {

	for (int dy = y; dy < y + SIZE; dy++) {
		for (int dx = x; dx < x + SIZE; dx++) {
			map[dy][dx] = color;
		}
	}

}

void DFS(int cnt) {
	

	if (cnt == 0) { pass = true; return; }
	if (pass) return;
	for (int y = 1; y <= 10; y++) {
		for (int x = 1; x <= 10; x++) {
			if (map[y][x] == 1) {
				for (int k = 5; k >= 1; k--) {
					if (paper[k] > 0 && is_print(y,x,k)) {
						print(y, x, k, 2);
						paper[k]--;
						DFS(cnt - k * k);
						if (pass) return;
						paper[k]++;
						print(y, x, k, 1);
					}
				}
				return;
			}
		}
	}


}

int main() {

	for (int i = 1; i <= 5; i++)
		paper[i] = 5;
	int cnt = 0;
	for (int y = 1; y <= 10; y++) {
		for (int x = 1; x <= 10; x++) {
			cin >> map[y][x];
			if (map[y][x] == 1)
				cnt++;
		}
	}

	if (cnt == 0)
		cout << 0;
	else
		DFS(cnt);

	for (int i = 1; i <= 5; i++) {
		ans = ans + 5 - paper[i];
	}
	if (ans == 0)
		cout << -1;
	else
		cout << ans;
}

zhh1020 4년 전 0

자답입니다.

반복문 ( k = 5 ~ k = 1) 를 돌고 나서 return을 해줘야 하며

cnt가 0일때 최소값 판단을 해줘야 합니다.

xodn0996 4년 전 0

50번째 줄에 return이 꼭 필요한가요?
잘 몰라서 물어보는 질문입니다!

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

문제

문제

출처

ICPC

색종이 붙이기 질문입니다.

zhh1020 4년 전 0

zhh1020 4년 전 0

xodn0996 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말