백준 17136번 색종이 붙이기 C++ 브루트포스 알고리즘, DFS, 백트래킹

리뷰

 

아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ 재귀 너무 싫다.

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

 

 

문제 풀이

1. input 함수를 통해 맵을 초기화 해주고 1의 총 개수를 변수 one에 저장해 준다. 색종이 5개도 각각 5개씩 저장해 준다.
2. dfs함수를 시작한다 매개변수로는 행, 붙힌 색종이 개수, 남은 1의 개수를 전달해 준다.
3. 당연하게도 기저조건은 맵에 1이 존재하지 않는 경우이다, 정답 ans를 갱신하고 리턴해 준다.
4. 만약 현재 붙힌 색종이 개수가 ans보다 크거나 같고, 25개 이상을 붙였다면 더 이상 탐색할 필요가 없다.
5. x행부터 탐색을 시작하여 1을 만날 경우 1~5번 인덱스의 색종이를 하나씩 대입해 본다.
6. 만약 i번째 색종이를 붙힐 수 있다면 색종이를 붙히고 해당 색종이의 개수를 한개 줄여준다.
7. 붙힌 색종이를 1 증가시키고, i * i개의 1을 remain에서 지워준 후 현재 행으로부터 재귀를 시작한다.
8. 재귀가 종료된 후엔 이전에 했던 작업들을 다시 원상복구 시켜준다, 재귀가 종료될때까지 계속 진행해 준다.
9. 만약 ans값이 초기값과 동일하다면 -1을 출력하고 아니라면 ans값을 출력해 주면 된다.

 

참고 사항

2차 배열을 탐색 중 1을 만나서 1~5의 색종이를 붙였다면 현재 재귀는 더 이상 탐색해 줄 필요가 없다.

이부분을 헤매서 계속 무한루프가 출력되었었다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
int lst[10][10];
int ans = 1e9; // 최대값 설정
int one = 0; // 1의 개수 저장용
int papers[6]; // 색종이 정보
int v[6] = { 0, }; // 방문처리용

void input() { // 맵 초기화, 1의 총 개수 초기화, 색종이 개수 초기화
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> lst[i][j];
            if (lst[i][j]) one++;
        }
    }
    for (int i = 1; i < 6; i++) papers[i] = 5;
}

bool chk(int index, int x, int y) { // index * index 색종이를 붙힐 수 있는지 체크
    for (int i = x; i < x + index; i++) {
        for (int j = y; j < y + index; j++) {
            if (!lst[i][j]) return false;
        }
    }
    return true;
}

void simul(int index, int x, int y) {
    for (int i = x; i < x + index; i++) {
        for (int j = y; j < y + index; j++) {
            lst[i][j] = 0;
        }
    }
}

void resimul(int index, int x, int y) {
    for (int i = x; i < x + index; i++) {
        for (int j = y; j < y + index; j++) {
            lst[i][j] = 1;
        }
    }
}

void dfs(int x, int total, int remain) { // 모든 색종이 사용해 보기
    if (!remain) { // 더 이상 1이 없다면 최소값 갱신 후 리턴
        ans = min(ans, total);
        return;
    }
    if (ans <= total || total > 25) return;
    for (int row = x; row < 10; row++) {
        for (int col = 0; col < 10; col++) {
            if (lst[row][col]) {
                for (int i = 5; i > 0; i--) { // 색종이 1 ~ 5 전부 중복 없이 사용해 보기
                    if (row + i <= 10 && col + i <= 10 && papers[i] && chk(i, row, col)) {
                        simul(i, row, col);
                        papers[i]--;
                        dfs(row, total + 1, remain - (i * i)); // 1을 0으로 바꾼 개수만큼 remain에서 빼준다.
                        resimul(i, row, col);
                        papers[i]++;
                    }
                }
                return;
            }
        }
    }
}

int main() {
    input();
    dfs(0, 0, one);
    if (ans == 1e9) cout << -1;
    else cout << ans;
}