[프로그래머스] 기둥과 보 설치 (C++)

기둥과 보 설치 (Level 3)

문제

전체 문제 보기

코딩테스트 연습 - 기둥과 보 설치

접근법

해당 문제는 카카오 블라인드 2020의 기출문제입니다. 카카오에서 공개한 해당 문제의 정답률은 1.9%로 매우 어려운 문제였습니다. 카카오는 해당 문제의 출제의도를 "주어진 조건에 맞게 정확하게 코드를 작성할 수 있는지 파악" 하기 위함 이라고 밝혔습니다.(카카오 공식 문제 해설) 이번 문제를 풀이하는데 있어서 특정 알고리즘 지식을 요구하지는 않습니다. 다만, 구현량이 상당히 많고 구현하는데 시간이 꾀나 오래 걸리기 때문에 문제의 난이도가 높았습니다.

 

구현하면서 가장 어려웠던 부분은 기둥 혹은 보를 해체하는 경우였습니다. 예를 들어 보를 해체한다고 했을 때 보의 4방향으로 기둥 및 보가 유효한지 확인해야하고 이는 꾀나 복잡한 작업입니다. 이를 단순화하기 위해서 기둥 혹은 보를 하나 해체할 경우 전체 기둥 혹은 보가 유효한지 확인하는 방식으로 문제를 해결하였습니다. 이는 문제의 조건에서 기둥 혹은 보의 개수를 최대 1000개까지로 제한하였기 때문에 가능했습니다.

 

기둥 혹은 보의 전체 탐색을 위해서 기둥 과 보를 Frame 클래스로 부터 상속받는 구조로 구현하였습니다. Frame 클래스로 부터 상속받은 보Board 클래스와 기둥Column클래로 구현고 전체 Frame들을 담을 vector<Frame*> 배열인 frames를 두어 하나의 Frame을 frames를 전체 탐색하여 유효한 삭제인지 확인하는 방식으로 구현하였습니다. 만약 유효하지 않은 해체라면 다시 Frame을 설치하였습니다.

 

기둥 혹은 보를 추가하는 것은 비교적 쉬운데 기둥 혹은 보를 생성한 후 해당 기둥 혹은 보의 유효성을 판단을 하고, 유효하다면 유지, 유효하지 않다면 해제하는 방식으로 구현하였습니다.

전체 소스 코드

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

struct Node{
    bool bBoard{};
    bool bColumn{};
};
using Map = vector<vector<Node>>;
class Frame{
public:
    Frame(Map& _map, int _x, int _y, int _type) : mMap(_map), x(_x), y(_y), type(_type){}
    virtual ~Frame() {};
    virtual bool IsValid() = 0;
    bool operator<(const Frame& other);
    bool IsEqual(int _x, int _y, int _type);
    int GetX() const {return x;}
    int GetY() const {return y;}
    int GetType() const {return type;}
protected:
    Map& mMap;
    int x;
    int y;
    int type;
};
bool Frame::IsEqual(int _x, int _y, int _type)
{
    return (x == _x) && (y == _y) && (type == _type);
}
bool Frame::operator<(const Frame& other)
{
    if(x < other.x) return true;
    else if(x == other.x && y < other.y) return true;
    else if(x == other.x && y == other.y && type < other.type) return true;
    return false;
}
class Board : public Frame{
public:
    Board(Map& map, int x, int y);
    ~Board() override;
    bool IsValid() override;
};
Board::Board(Map& map, int x, int y) 
    : Frame(map, x, y, 1) 
{
    //cout << x << "," <<y<<" 에 보 설치" << endl;
    mMap[x][y].bBoard = true;
}
Board::~Board()
{
    //cout << x << "," <<y<<" 에 보 해체" << endl;
    mMap[x][y].bBoard = false;  
}
bool Board::IsValid()
{
    const int N = mMap.size();
    bool retval = false;
    // 왼쪽 아래에 기둥이 있는 경우
    if(y > 0 && mMap[x][y-1].bColumn)
        retval = true;
    // 오른쪽 아래에 기둥이 있는 경우
    else if(y > 0 && x < N - 1 && mMap[x+1][y-1].bColumn)
        retval = true;
    // 양쪽에 보가 있는 경우
    else if(x > 0 && x < N - 1 && mMap[x-1][y].bBoard && mMap[x+1][y].bBoard)
        retval = true;
    //cout << "유효성 검사: "<< x <<"," <<y << " 보 " << retval << endl;
    return retval;
}
class Column : public Frame{
  public:
    Column(Map& map, int x, int y);
    ~Column() override;
    bool IsValid() override;
};
Column::Column(Map& map, int x, int y)
    : Frame(map, x, y, 0) 
{
    //cout << x << "," <<y<<" 에 기둥 설치" << endl;
    mMap[x][y].bColumn = true;       
}
Column::~Column()
{
    //cout << x << "," <<y<<" 에 기둥 해체" << endl;
    mMap[x][y].bColumn = false;
}

bool Column::IsValid()
{
    const int N = mMap.size();
    bool retval = false;
    // 기둥이 바닥인 경우
    if(y == 0)
        retval = true;
    // 기둥 아래에 다른 기둥이 있는 경우
    else if(y > 0 && mMap[x][y-1].bColumn)
        retval = true;
    // 기둥 아래에 보의 왼쪽편이 있는 경우
    else if(mMap[x][y].bBoard)
        retval = true;
    // 기둥 아래에 보의 오른쪽편이 있는 경우
    else if(x > 0 && mMap[x-1][y].bBoard)
        retval = true;

    //cout << "유효성 검사: "<< x <<"," <<y << " 기둥 " << retval << endl;
    return retval;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;

    Map map(n + 1, vector<Node>(n+1));


    vector<Frame*> frames;
    for(const auto& cmd : build_frame)
    {
        //cout <<"명령: " << cmd[0] << "," << cmd[1] << "에 " << cmd[2] << "를 " << cmd[3] << endl; 

        if(cmd[3] == 0) // 삭제
        {
            auto iter = frames.begin();
            while(iter != frames.end())
            {
                if((*iter)->IsEqual(cmd[0], cmd[1], cmd[2]))
                {
                    //cout << (*iter)->GetX() << "," << (*iter)->GetY() << "발견" << endl;

                    iter_swap(iter, frames.end() - 1);
                    delete frames.back();
                    frames.pop_back();
                    break;
                }
                iter++;
            }
            // 모든 프레임들에 대한 유효성 검사
            for(auto frame : frames)
            {
                // 유효하지 않은 명령이라면 복구
                if(frame->IsValid() == false)
                {
                    if(cmd[2] == 0)// 기둥
                        frames.emplace_back(new Column(map, cmd[0], cmd[1]));
                    else    // 보
                        frames.emplace_back(new Board(map, cmd[0], cmd[1]));                    
                    break;
                }
            }

        }
        else // 설치
        {
            if(cmd[2] == 0)// 기둥
                frames.emplace_back(new Column(map, cmd[0], cmd[1]));
            else    // 보
                frames.emplace_back(new Board(map, cmd[0], cmd[1]));

            // 유효성 검사
            if(frames.back()->IsValid() == false)
            {
                delete frames.back();
                frames.pop_back();
            }

        }
    }

    auto comp = [](Frame* lhs, Frame* rhs)
    {
        return (*lhs) < (*rhs);  
    };
    sort(frames.begin(), frames.end(), comp);
    answer.reserve(frames.size());
    for(auto frame : frames)
    {
        answer.push_back({frame->GetX(), frame->GetY(), frame->GetType()});
        delete frame; // 동적할당한 frame들 해제
    }
    return answer;
}

결과