[브루트 포스 / BOJ 14620 / C++] 꽃길

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

14620번: 꽃길

1) 빈칸 중 3개를 뽑는 경우를 모두 찾는다.
2) 각 경우마다 씨앗을 심는다. 그리고 꽃이 폈을때(즉, 상하좌우를 확인할때) 조건에 맞는지 확인한다.
3) 만약 확인한 경우가 잘못됐다면, 다른 경우로 넘어가고, 아니라면 총 비용을 계산해서 최소값인지 확인한다.

 

 이 문제는 전형적인 완전 탐색 문제이다! 이 문제의 시간복잡도는 아무리 커도 20만을 넘기지 않는다.

(100 combination 3 = 대략 16만)

 

완전 탐색의 기본 구조를 정리하자면,

 

go(here){

 

vis[here] = 1; // 현위치 방문

go(here+1); // 다음꺼 확인

vis[here] = 0; // 현위치 돌려주기

 

}

 

정도로 정리할 수 있을 것이다.

 

문제 나온대로 그대로 구현해보자.

 

먼저 빈땅 3개를 뽑는 경우의 수를 센다.

 

우선 10개 중에 3개를 뽑는 경우는 3중 for문이나 재귀적으로 해결해야한다.

 

combi(int n, vector<int> v){

 if(v.size()==3) -> 3개를 모두 뽑았다면 이때 종료 

 

for(i = n+1부터 10까지){

 v.push_back(i); // 새로운 상태로 업데이트

combi(i, v); // 다음꺼 확인

v.pop_back(); // 현 상태 돌려주기

 

}

}

 

이 구조만 이해했다면 다음은 매우쉽게 구현할 수 있다!!

 

들어온 3개의 좌표 각각에 대해 상하좌우를 확인하고 비용을 구해주면 끝이다!

 

코드를 보며 천천히 이해해보자~!

 

#include <bits/stdc++.h>

using namespace std;

int N, G, res=INT_MAX;
int bd[12][12];
int vis[12][12];
vector<pair<int,int>> ps;

int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};


void chk(vector<int> v){
    memset(vis, 0, sizeof(vis)); // vis 초기화
    
    int costs = 0; // 총 비용은 0
    
    for(int j = 0 ; j < 3 ; j++){
        int y = ps[v[j]].first;
        int x = ps[v[j]].second;
            
        vis[y][x] = 1; //현위치 표시
        costs += bd[y][x]; // 시작위치 비용
        
        for(int i = 0 ; i < 4 ; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny >= N || nx >= N || ny < 0 || nx < 0) return; // 꽃밭넘어가면 의미없음.
            if(vis[ny][nx]) return; // 이미 차지된 자리라면 의미없음.
            
            vis[ny][nx] = 1; // 꽃잎 표시
            costs += bd[ny][nx]; // 해당 위치들 비용
        }
    }
    
    res = min(costs, res); // 최소 비용 구하기
    
}

void solve(int n, vector<int> v){
    if(v.size()==3){
        chk(v);
        return;
    }
    
    for(int i = n+1; i < ps.size(); i++){
        v.push_back(i);
        solve(i, v);
        v.pop_back();
    }
    
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> bd[i][j];
            ps.push_back({i,j});
        }
    }
    
    vector<int> v;
    solve(-1, v);
    
    cout << res;
    
}