컴공댕이 공부일지

[ 브루트포스 ] 도전 과제-1 ( 백준 14620 꽃길 c++) 본문

기록/알고리즘 스터디 알튜비튜 5기✨

[ 브루트포스 ] 도전 과제-1 ( 백준 14620 꽃길 c++)

은솜솜솜 2023. 9. 13. 13:41
728x90

 

 

꽃을 심을 좌표를 찾는 과정이 매우매우... 험난했다.....

 

몫과 나머지를 활용하는 방법도 있는데

일단은 무식하게 6중 반복문으로 풀어보았다!

 

#include <iostream>
#include <algorithm>


using namespace std;

int groundCost[10][10];


//꽃 심는 좌표가 주어지면, 그 꽃의 가격 구하는 함수.
int calCost(int x, int y ) {
    
    int cost=groundCost[x][y]
            +groundCost[x-1][y]
            +groundCost[x+1][y]
            +groundCost[x][y-1]
            +groundCost[x][y+1];
        

    return cost;
}



//꽃 심는 좌표 3개가 주어지면, 죽는지 여부 판별하는 함수.
bool death(int x[3], int y[3]) {
    
    //x,y 좌표의 차가 3이상이어야 안죽어. 최소 3칸은 떨어져서 심어야 함.

    for(int i=0; i<2; i++) {
        int subX = abs(x[i]-x[i+1]); 
        int subY = abs(y[i]-y[i+1]); 
        if(subX+subY<3) {
            return true; //꽃 죽었다.
        }
    }
    
    int subX = abs(x[0]-x[2]); 
    int subY = abs(y[0]-y[2]);
    if(subX+subY<3) {
        return true; //꽃 죽었다.
    }

    return false; //위 경우 모두 아니라면, 꽃 살았다.
}



//꽃 심기
int plant(int n) {

    int res=0;
    int lastRes=0;
    int count=0;
    //꽃 심는 위치
    int x[3]={0,0,0};
    int y[3]={0,0,0};
    
    
    //꽃 심을 3개의 좌표 설정 : 완전탐색
    //꽃은 가장 테두리엔 심지 않는다. 1 ~ n-2만 탐색
    for (int x1 = 1; x1 <= n-2; x1++) {
        for (int y1 = 1; y1 <= n-2; y1++) {
            for (int x2 = 1; x2 <= n-2; x2++) {
                for (int y2 = 1; y2 <= n-2; y2++) {
                    
                     if (x1 == x2 && y1 == y2) {
                         continue;
                    }
                    
                    for (int x3 = 1; x3 <= n-2; x3++) {
                        for (int y3 = 1; y3 <= n-2; y3++) {
                            // 중복되지 않는 좌표인지 확인
                            if ((x1 == x3 && y1 == y3) || (x2 == x3 && y2 == y3)) {
                                 continue;
                            }
                            
                            x[0]=x1;
                            x[1]=x2;
                            x[2]=x3;
                            
                            y[0]=y1;
                            y[1]=y2;
                            y[2]=y3;
                            
                            
                            if(!death(x, y)) { //세 꽃이 죽지 않으면
                                    
                                res = 0; //현재 구할 변수는 초기화
                            
                                //꽃 3송이 심는 데 드는 땅가격 계산
                                for(int i=0; i<3; i++) {
                                    res+=calCost(x[i], y[i]);
                                }
                                

                                if(lastRes!=0) { //지난번 땅값 0이 아니라면, 즉 한번이라도 구해졌다면,
                                    res=min(lastRes,res);
                                }
                                                    
                                lastRes = res; //지난 최솟값 저장해두고,
                        
                            }
                                
                        }
                    }
                }
            }
        }
    }
    
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    int res;

    //입력
    cin >> n;

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> groundCost[i][j];
        }
    }
    
    //연산
    res = plant(n);
    
    
    //출력
    cout << res << "\n";
    
    return 0;
}

 

 

지난주 과제였는데 풀다풀다 안풀려서 접어뒀다가...

다시 접근해서 겨우 풀었따... 존버는승리한다.... 9월19일새벽에결국해내다...

 

지난주 수업을 결석했어서, 이 결석을 면제받기 위해 다섯 문제를 다 풀었어야 했는데

얘만!! 너무 안풀려서ㅠㅠ 진짜 결국 미완성으로 내버렸는데

다행히 도전 문제라 한 번의 제재출 기회를 받았다..... 하아......

 

알튜비튜 쉽지 않아서.. 진짜 던질까.. 제명당할까..싶은 ㅋㅋ ㅠㅠ 생각도 들지만.. 이번주도 통과..!ㅠㅠ 

728x90
Comments