[백준] 17136번: 색종이 붙이기

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

17136번: 색종이 붙이기

 

문제 이해

처음에는 그냥 단순히 하나하나 가능한 최대 크기의 색종이를 붙이는 식으로 했더니 예제는 다 통과되는데 내자마자 틀렸습니다가 떴다. 여기에 대한 반례가 하나 있는데

 

이렇게 되어 있으면 왼쪽 상단부터 시작을 하기 때문에

이렇게 채워진다

근데 사실 정답은

이거다, 그래서 각 좌표별로 붙일 수 있는 최대 크기의 색종이를 그냥 지정하면 안되고, 1인 경우에 사이즈1부터 5까지의 색종이들을 다 한번씩 넣어봐야 한다.

즉, DFS로 문제를 풀어야 하는 것이다.

 

이 DFS가 조금 헷갈렸는데 요점만 설명하자면

1. 종료 조건

• 만약 min 색종이 개수보다 현재까지 붙인 색종이 수가 같거나 많으면 가볼 필요 없는 경우이므로 return한다
• 만약 모든 칸에 색종이를 붙인 경우라면 return 한다. --> 이거 안해주면 만약 (9,9)가 1인 경우 색종이를 붙이고 min값에 비교를 못하게 된다.

2. 재귀

• 색종이를 붙일 다음 위치를 찾는다. 전에 붙인 위치는 인자(y, x)로 받았으니까 거기서부터 1인 곳을 찾아주면 된다.

• for (; i < 10; i++) {
    for (; j < 10; j++) {
      if (map[i][j] == 1) {
        find = 1;
        break;
      }
      if (i >= 9 && j >= 9) {
        if (cnt < min) min = cnt;
        return;
      }
    }
    if (find == 1) break;
    j = 0;
  }

• 찾았으면 그 위치에 색종이를 붙여야 한다. 사이즈 5부터 1까지의 색종이를 붙이는 모든 경우의 수를 봐야한다.
• 그 사이즈이 색종이가 안들어가면 continue, 그 사이즈 색종이가 더이상 안남았으면 continue한다
• 그 크기의 색종이가 이 칸에 들어간다면 붙이고(Cover()), 남은 붙여야 하는 칸 개수(pcnt)를 줄이고, 남은 색종이 개수 배열(paper)도 줄여준다 다음 색종이 붙일 위치를 찾아 DFS를 다시 call한다
• DFS에서 돌아왔으면 맵(Uncover())과 남은 붙여야하는 칸의 개수(pcnt), 남은 색종이 개수 배열(paper)를 복구해준다.

• for (int k = 5; k >= 1; k--) {
    if (!Check(i, j, k)) continue; // 이 크기 못붙임
    if (paper[k] <= 0) continue; // 색종이 안남아있음 -> 못붙임
    Cover(i, j, k);
    pcnt -= k * k;
    paper[k]--;
    DFS(i, j + 1, cnt + 1); // 다음 위치부터 탐색
    paper[k]++;
    pcnt += k * k;
    Uncover(i, j, k);
  }

 

전체 코드

#include <stdio.h>
#include <string.h>
#define INF 0x7fffffff

int map[10 + 2][10 + 2];
int paper[5+2] = { 0, 5, 5, 5, 5, 5 };
int min = INF;
int pcnt;

void Get_Input(void) {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) pcnt++;
		}
	}
}

int Check(int y, int x, int len) {
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			if (map[y+i][x+j] != 1) return 0;
		}
	}
	return 1;
}

void Cover(int y, int x, int len) {
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			map[y+i][x+j] = (len+10);
		}
	}
}

void Uncover(int y, int x, int len) {
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			map[y + i][x + j] = 1;
		}
	}
}

void Print_Map(void) {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			printf("%2d ", map[i][j]);
		} 
		printf("\n");
	}
	printf("\n");
}

void DFS(int y, int x, int cnt) {
	int i = y, j = x;
	int find = 0;
	if (cnt >= min) return;
	if (pcnt == 0) {
		if (cnt < min) min = cnt;
		return;
	}
	// 재귀
	// 1. 색종이 붙일 다음 위치 찾기
	for (; i < 10; i++) {
		for (; j < 10; j++) {
			if (map[i][j] == 1) {
				find = 1;
				break;
			}
			if (i >= 9 && j >= 9) {
				if (cnt < min) min = cnt;
				return;
			}
		}
		if (find == 1) break;
		j = 0;
	}

	for (int k = 5; k >= 1; k--) {
		if (!Check(i, j, k)) continue; // 이 크기 못붙임
		if (paper[k] <= 0) continue; // 색종이 안남아있음 -> 못붙임
		Cover(i, j, k);
		pcnt -= k * k;
		paper[k]--;
		DFS(i, j + 1, cnt + 1); // 다음 위치부터 탐색
		paper[k]++;
		pcnt += k * k;
		Uncover(i, j, k);
	}

}

int main(void) {
	Get_Input();
	DFS(0, 0, 0);
	if (min == INF) printf("-1");
	else printf("%d", min);
	return 0;
}