글 읽기 - 시간이 어느부분에서 많이 걸리는지 알고 싶습니다

kysu5095 4년 전 0

제가 푼 방식을 설명 드리겠습니다

1. 입력을 받을 때 색종이를 채워야 할 칸(res_cnt) 를 구함

2. 92줄 find_color 함수로 진입

- 각 칸에 최대로 채울 수 있는 색종이의 개수로 맵 초기화

3. dfs 진입

- dfs 종료 조건 : 현재까지 구한 최소의 색종이 개수(res_cnt)보다 많이 사용(_use)하면 return

채울 수 있는 모든 곳을 색종이로 덮었을 경우 res_cnt 변경 후 return

해당 칸에서 1*1 색종이까지 모두 사용했을 경우 return

- 임시배열(tmp_arr)에 현재 맵의 상태를 복사

- for문을 돌면서 색종이가 들어갈 수 있는 칸을 찾음

- 현재 칸의 최대 개수 k 부터 1까지 for문 --

- 색종이 남아있는지 확인 && 채울 수 있는지 확인(is_available)

- 배열 0으로 만들고 색종이 하나 줄이고 dfs 진입

이런 방식으로 풀었습니다.

초기 find_color함수로 최대로 넣을 수 있는 색종이 개수를 미리 구함으로 써 5칸부터 확인하는 것을 줄였는데

생각보다 실행 시간이 많이 나오더라구요.

제가 예상한 것은 dfs진입 후 임시 배열을 복사하는 것인데 이게 이렇게 오래걸리는 일인지

또 다른 곳에서 시간을 잡아 먹는 곳이 있다면 설명 부탁 드립니다. 감사합니다.

// 복습 - 색종이 붙이기
// 4:50 시작

#include <iostream>
#include <string.h>
#include <limits.h>

using namespace std;

int res = 26, res_cnt = 0;
int arr[10][10];
int color_paper[6] = { 0, 5, 5, 5, 5, 5 };

bool is_available(int y, int x, int s) {
	for (int i = y; i < y + s; i++) {
		for (int j = x; j < x + s; j++) {
			if (!arr[i][j])
				return false;
		}
	}
	return true;
}

void dfs(int y, int x, int _use, int _cnt) {
	// 현재 최소 사용한 색종이보다 많이 사용하면 return
	if (_use > res) return;
	// 판의 모든 곳을 색종이로 덮으면 값 초기화
	if (_cnt == res_cnt) {
		res = _use;
		return;
	}
	int val;
	// 기존 배열 복사
	int tmp_arr[10][10];
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			tmp_arr[i][j] = arr[i][j];

	int i = y;
	int j = x;
	for (i = y; i < 10; i++) {
		for (j = x; j < 10; j++) {
			if (arr[i][j]) {
				val = arr[i][j];
				for (int k = val; k >= 1; k--) {
					if (color_paper[k] && is_available(i, j, k)) {
						// 해당 사이즈만큼 0으로 만들어 줌
						for (int l = i; l < i + k; l++) 
							for (int m = j; m < j + k; m++) 
								arr[l][m] = 0;
						color_paper[k]--;

						dfs(i, j, _use + 1, _cnt + (k * k));

						// dfs 이전 상태로 회귀
						for (int l = i; l < i + k; l++) 
							for (int m = j; m < j + k; m++) 
								arr[l][m] = tmp_arr[l][m];
						color_paper[k]++;
					}
				}
				return;
			}
		}
		x = 0;
	}
	return;
}

void find_color() {
	// 해당 칸에 최대로 들어갈 수 있는 색종이의 개수를 구함
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (arr[i][j]) {
				for (int k = 5; k >= 1; k--) {
					if (i + k > 10 || j + k > 10)
						continue;
					if (is_available(i, j, k)) {
						arr[i][j] = k;
						break;
					}
				}
			}
		}
	}
	dfs(0, 0, 0, 0);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> arr[i][j];
			if (arr[i][j]) res_cnt++;
		}
	}
	find_color();

	if (res == 26)
		cout << -1 << '\n';
	else
		cout << res << '\n';
	return 0;
}    

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