이코테, 프로그래머스 - 기둥과 보 설치

문제

https://school.programmers.co.kr/learn/courses/30/lessons/60061

프로그래머스

command 리스트에 따라 주어진 조건에 맞게 기둥과 보를 설치/해제하는 문제였다.

 

조건

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

---

문제 풀이

처음에 문제를 잘못 이해해서 다시 풀었다... 보의 양 끝이 하나의 보를 말하는게 아니라 이어진 전체 보의 양 끝을 의미하는 것으로 이해하는 바람에 vector<vector<vector<pair>>>> 형태의 map을 만들어서 복잡하게 풀었다. 풀다 보니 너무너무 복잡해서 이거 아닌거 같은데..? 하는 마음으로 다른 사람의 풀이를 찾아보니 하나의 보의 양 끝을 의미하는 것이었다..! ㅋㅋ 마음을 가다듬고 처음부터 다시 풀었고 100점을 맞았다. 하하

 

설치 시에는 조건을 만족한다면 바로 설치하고, 삭제 시에는 일단 삭제 후 map이 이상해지지 않았는지 전체 점검을 한 후 이상해졌다면 복구하는 방법을 사용해서 문제를 해결했다. 처음에는 삭제 시에도 조건을 정해주고 만족하면 삭제하도록 풀었는데, 다른 사람들의 풀이를 참고하니 이 방법이 더 깔끔한 것 같아서 바꿨다.

 

#include <string>
#include <vector>

using namespace std;

bool map[101][101][2]={false}; //x, y, 기둥/보 여부 0: 기둥 1: 보
int mapSize;

bool sizeCheck(int x,int y){
    if(x < 0 || y < 0 || x > mapSize || y > mapSize){
        return false;
    }
    return true;
}

bool isCanInstall(int x, int y, int type){
    //기둥    
    if(type == 0){
        if(y==0){ //바닥에 설치
            return true;
        }
        else if(sizeCheck(x,y-1) && map[x][y-1][0]){ //아래가 기둥이면
            return true;
        }
        else if(map[x][y][1] || (sizeCheck(x-1, y) && map[x-1][y][1])){ //아래가 보
            return true;
        }
    }
    //보
    else{
        if((sizeCheck(x,y-1) && map[x][y-1][0]) || (sizeCheck(x+1,y-1) && map[x+1][y-1][0])){ //아래가 기둥
            return true;
        }
        if((sizeCheck(x-1,y) && sizeCheck(x+1,y) && map[x-1][y][1] && map[x+1][y][1])){ //양 옆이 보
            return true;
        }
    }
    return false;
}

bool isCanUninstall(){
    for(int i=0;i<=mapSize;i++){
        for(int j=0;j<=mapSize;j++){
            for(int k=0;k<2;k++){
                if(map[i][j][k] == 1){
                    if(!isCanInstall(i,j,k)) return false;
                }
            }
        }
    }
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    int i,j;
    int x,y,a,b;
    mapSize = n;
    int commandSize = build_frame.size();
    
    for(i=0;i<commandSize;i++){
        x = build_frame[i][0];
        y = build_frame[i][1];
        a = build_frame[i][2];
        b = build_frame[i][3];
        
        if(b == 1){ //설치
            // printf("install x: %d y: %d a: %d\n", x,y,a);
            if(isCanInstall(x,y,a)){
                // printf("설치\n");
                map[x][y][a] = true;
            }
        }
        else{ //삭제
            // printf("uninstall x: %d y: %d a: %d\n", x,y,a);
            map[x][y][a] = false; //일단 먼저 삭제
            if(!isCanUninstall()) {
                map[x][y][a] = true;
            }
            // else printf("삭제\n");
        }
    }
    
    int answerCnt=0;
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
            for(int k=0;k<2;k++){
                if(map[i][j][k] == true){
                    vector<int> answerRow;
                    answerRow.push_back(i);
                    answerRow.push_back(j);
                    answerRow.push_back(k);
                    answer.push_back(answerRow);
                }
            }
        }
    }
    
    
    return answer;
}

 

문제 제대로 읽고 제대로 이해하기 + 깔끔하게 풀기! 노력하자~