Inflearn Community Q&A

안녕하세요 지민님 ㅎㅎ 깊게 잘 생각하셨네요

Q1. DFS 함수를 int형 반환값으로 구현하고 상하좌우 네 방향으로 탐색할 때, 단순 DFS 완전탐색과 DP 구조로는 해결이 어려운 이유는 무엇인가?

-> 단순히 4방향이라서 DP가 불가능하지 않습니다. DP가 힘든경우는 해당 배열을 선언하기가 어려워서 안하곤 합니다.

이 문제의 경우 DP정의가 매우 까다롭습니다.

    int& ret = dp[r][c][remOne]; 

지민님이 만든 DP의 의미가 좀 모호한게 r, c까지 채웠을 때 remOne이 2이라는 의미자체는 전체칸에서 어떤 칸이 색종이로 안뒤덮혀있는가? 에 대한 상태를 파악하기가 어려운 것 같습니다. 이 때문에 보드의 상태가 정확히 메모이제이션이 안될 것 같습니다.

Q2. 시간복잡도를 줄이기 위해 DP 적용가능 여부. 첫 풀이 시도가 틀린 이유는?

A. 이 문제에서 상태값은, "현재 y좌표, 현재 x좌표, 남은 1의 개수, 지금까지 붙여온 종이의 배치 구조" 가 필요하다. (이걸 다 저장한다면 부분 최적해가 보장되어 dp 사용가능하다고 이해했습니다.)

-> 비슷합니다. 만약 DP로 만들거면 보드의 상태, 각 색종이의 상태 이정도면 가능할 것 같습니다.

한번 만들어볼까요?

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int N = 10;

// dp 메모이제이션: key = (board 상태, p1, p2, p3, p4, p5)
// dp 함수: 현재 board 상태와 각 색종이 사용 횟수를 인자로 받아, 남은 '1'을 덮기 위한 최소 색종이 수를 반환
unordered_map<string, int> memo;

// 보드 + 색종이 상태값 인코딩
string encode(const string &board, int p1, int p2, int p3, int p4, int p5) {
    return board + "#" + to_string(p1) + "," + to_string(p2) + "," + to_string(p3) + "," + to_string(p4) + "," + to_string(p5);
}
 
int solve(string board, int p1, int p2, int p3, int p4, int p5) { 
    int pos = board.find('1');
    if (pos == string::npos) return 0; 
    string key = encode(board, p1, p2, p3, p4, p5);
    if (memo.find(key) != memo.end()) return memo[key];
    
    int ans = INF;
    int row = pos / N;
    int col = pos % N; 
    for (int s = 5; s >= 1; s--) { 
        int used;
        if (s == 1) used = p1;
        else if (s == 2) used = p2;
        else if (s == 3) used = p3;
        else if (s == 4) used = p4;
        else used = p5;
        if (used >= 5) continue;     
        if (row + s > N || col + s > N) continue;
        bool canPlace = true;
        for (int i = 0; i < s && canPlace; i++) {
            for (int j = 0; j < s; j++) {
                int idx = (row + i) * N + (col + j);
                if (board[idx] != '1') {
                    canPlace = false;
                    break;
                }
            }
        }
        if (!canPlace) continue; 
        string newBoard = board;
        for (int i = 0; i < s; i++) {
            for (int j = 0; j < s; j++) {
                int idx = (row + i) * N + (col + j);
                newBoard[idx] = '0';
            }
        } 
        int res;
        if (s == 1)
            res = solve(newBoard, p1 + 1, p2, p3, p4, p5);
        else if (s == 2)
            res = solve(newBoard, p1, p2 + 1, p3, p4, p5);
        else if (s == 3)
            res = solve(newBoard, p1, p2, p3 + 1, p4, p5);
        else if (s == 4)
            res = solve(newBoard, p1, p2, p3, p4 + 1, p5);
        else // s == 5
            res = solve(newBoard, p1, p2, p3, p4, p5 + 1);
        
        if (res != INF) {
            ans = min(ans, res + 1);
        }
    }
    
    memo[key] = ans;
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    // 보드 상태를 DP에 넣기 위해 string으로 쉽게
    string board;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            int cell;
            cin >> cell;
            board.push_back(cell ? '1' : '0');
        }
    } 
    int res = solve(board, 0, 0, 0, 0, 0);
    cout << (res == INF ? -1 : res);
    return 0;
}

해당코드 참고부탁드립니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.