백준 17136번 색종이 붙이기

https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

 

 

 

 

<접근방법>

백트래킹 문제입니다.

백트래킹의 골격이 뭔지 알 수 있는 문제였던 것 같습니다.

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 987654321;
int map[11][11], len[5] = {5, 5, 5, 5, 5};
int n = 10;
int res = INF;
int one_num;


void dfs(int dep, int point, int cnt) {
	if (dep == one_num) {
		res = min(res, cnt);
		return;
	}
	if (cnt > res) return;

	int y = point / 10;
	int x = point % 10;

	if (map[y][x] == 0) {
		dfs(dep, point+1, cnt);
		return;
	}

	for (int z = 4; z >= 0; z--) {
		int ty = y + z;
		int tx = x + z;
		if (ty >= n || tx >= n) continue;
		if (len[z] == 0) continue;
		
		bool flag = true;
		for (int i = y; i <= y + z; i++) {
			for (int j = x; j <= x + z; j++) {
				if (map[i][j] == 0) {
					flag = false;
					break;
				}
			}
		}

		if (!flag) continue;

		for (int i = y; i <= y + z; i++) {
			for (int j = x; j <= x + z; j++) {
				map[i][j] = 0;
			}
		}
		len[z]--;
		int width = (z + 1)*(z + 1);

		dfs(dep +  width, point + z, cnt + 1);

		len[z]++;
		for (int i = y; i <= y + z; i++) {
			for (int j = x; j <= x + z; j++) {
				map[i][j] = 1;
			}
		}
	}
}

int main() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) one_num++;
		}
	}

	dfs(0, 0, 0);

	if (res == INF) cout << -1 << '\n';
	else cout << res << '\n';

	return 0;
}

 

 

---

 

 

<느낀 점>

-이차원 배열 매개변수는 참조형이다