[BaekJoon/백준] 14620번 꽃길

 

토글 형식의 DFS를 사용하는 문제이다.

 

전체 N * N 배열에서, 3개의 꽃을 심을 모든 경우의 수를 탐색하기 때문.

 

 

시간초과가 한참 떠서,, 맞왜틀과의 시간을 가졌는데

3개를 뽑고 난 이후 BASE CASE에서 return을 안 쳐주는 실수를 했기 때문이었다 ㅜ.ㅜ

#include <iostream>

using namespace std;

int COST[10][10];

bool visit[10][10]; // 꽃의 영역 체크. visit[i][j] = true / dfs() / visit[i][j] = false 로직을 사용할 것임.

// 제자리, 상하좌우
int mx[5] = {0, 1, -1, 0, 0};
int my[5] = {0, 0, 0, 1, -1};

int N; // 화단 한 변의 길이

int MIN_COST = 20000;

int TOTAL_COST;


void CALCULATE() {
            
    if(MIN_COST > TOTAL_COST)
        MIN_COST = TOTAL_COST;
    
}

// 토글식 dfs를 사용해야 하는 경우임.
void dfs(int start, int K) { // K는 심은 갯수
    
    
    if(K == 3) {
        // 세 개 다 심음
        
        CALCULATE();
        
        return; // 이거 안넣어줘서 시간초과 났다..
    }
    
    
    int tx, ty;
    
    // N x N 화단 배열을 하나의 숫자 진행으로 나열
    
    for(int i = start; i < N * N; i++) {
        
        // 우선 현재 위치에 심었을 때, 맵을 벗어나지 않으려면 현재 위치를 중심으로, 십자가가 맵을 벗어나지 않아야 함.
        // 또한, 해당 위치가 이미 방문한 곳이 아니어야 함.
        
        bool flag = true; // 맵을 벗어나는지 체크.
        
        for(int x = 0; x < 5; x++) {
            
            tx = (i / N) + mx[x];
            ty = (i % N) + my[x];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= N) {
                flag = false; // 맵을 벗어난다는 것
                break;
            }
            
            if(visit[tx][ty]) {// 이미 영역이 차지되어 있다면
                flag = false;
                break;
            }
            
        }
        
        if(flag) {
            
            // 심어도 된다.
            
            
            // 심음
            for(int x = 0; x < 5; x++) {
                
                tx = (i / N) + mx[x];
                ty = (i % N) + my[x];
                
                visit[tx][ty] = true;
                
                TOTAL_COST += COST[tx][ty];
            }
            
            dfs(i + 1, K + 1);
            
            // 해제
            for(int x = 0; x < 5; x++) {
                
                tx = (i / N) + mx[x];
                ty = (i % N) + my[x];
                
                visit[tx][ty] = false;
                
                TOTAL_COST -= COST[tx][ty];

            }
        }
    }
}

int main() {
    
    
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            
            cin >> COST[i][j];
        }
    }
    
    dfs(0, 0);
    
    
    cout << MIN_COST << "\n";
    
}