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

문제

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

풀이

2차원 좌표 평면 상에서 기둥과 보를 설치하고, 그에 따라 가능한 구조물들을 반환하는 문제이다. 시뮬레이션 문제인데, 코드로 구현하는 과정이 어렵게 느껴졌다. 구조물을 설치하는 규칙은 다음과 같다.

• 기둥은 바닥 위 or 보의 한쪽 끝 부분 위 or 다른 기둥 위에 설치
• 보는 한쪽 끝 부분이 기둥 위 or 양쪽 끝 부분이 다른 보와 동시에 연결되어 설치

문제 해석 중 햇갈리는 부분이 있었는데, "기둥은 보의 한쪽 끝 부분 위에 있다"라는 조건을 "만약 보가 여러개 놓인 상황이면 보의 양 끝에만 기둥이 설치할 수 있다" 라고 해석했는데 이게 아니었다..

즉, 요렿게도 설치될 수 있다 (ㅡㅡㅣㅡㅡ)

구조물 설치를 위해서 bool structs[y][x][0 or 1] 배열을 사용했다. 0은 기둥을, 1은 보를 말한다. 처음에는 기둥과 보의 양끝 좌표를 모두 관리할려 했는데, 구현하다보니 그럴 필요가 없었다.

문제는 삭제 부분이었다. 기둥 또는 보를 삭제하면 붙어있는 구조물들만 확인하면 될것 같아보였지만, 도저히 로직이 안그려져서 해당 구조물을 삭제하고 전체 구조물이 위 조건에 맞는지 즉, 전체를 탐색하는 방법으로 구현했다. 처음에는 map<tuple<int, int, int>>로 구조물들을 받고 순회를 하는 방식으로 구현했지만, 테스트케이스 1번을 제외한 나머지가 시간 초과가 나왔다. set이나 vector로 바꿔도 마찬가지였다.

결국 인터넷을 찾아봤고 (아래 블로그 참조) structs 배열을 그대로 이용해서 구현할 수 있었다. map이나 set을 순회하는 것보다 2차원 배열이 빠를지는 몰랐다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool structs[101][101][2];


vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    
    for(int i = 0; i < build_frame.size(); i++){
        int x = build_frame[i][0];
        int y = build_frame[i][1];
        
        int kind = build_frame[i][2];
        int type = build_frame[i][3];
        
        // 설치
        if(type == 1){
            // 기둥
            if(kind == 0){
                // 바닥 or 보의 한쪽 끝 or 밑에 기둥이 있는지
                if(y == 0 || (structs[y][x][1] || structs[y][x-1][1]) || structs[y - 1][x][0]){
                    structs[y][x][kind] = true;
                }
            }
            // 보
            else{
                // 보를 설치할 위치의 한쪽 끝에 기둥이 있거나, 양쪽에 보가 있거나
                if((structs[y - 1][x][0] || structs[y - 1][x + 1][0]) || (structs[y][x-1][1] && structs[y][x+1][1])){
                    structs[y][x][kind] = true;
                }
            }
        }
        // 삭제
        else{
            structs[y][x][kind] = false;
            bool flag = true;
            
            for(int i = 0; i <= n; i++){
                for(int k = 0; k <= n; k++){
                    for(int j = 0; j < 2; j++){
                        if(structs[i][k][j]){
                            
                            // 기둥이라면
                            if(j == 0){
                                if(i == 0 || (structs[i][k][1] || structs[i][k-1][1]) || structs[i - 1][k][0]){
                                    continue;
                                }else{
                                    flag = false;
                                    break;
                                }
                            }
                            // 보라면
                            else{
                                if((structs[i - 1][k][0] || structs[i - 1][k + 1][0]) || (structs[i][k-1][1] && structs[i][k+1][1])){
                                    continue;
                                }else{
                                    flag = false;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
            if(!flag) structs[y][x][kind] = true;
        }
        
        
    }

    
    for(int i = 0; i <= n; i++){ // x 좌표
        for(int k = 0; k <= n; k++){ // y 좌표
            for(int j = 0; j < 2; j++){
                if(structs[k][i][j]){
                    vector<int> tmp;
                    tmp.push_back(i);
                    tmp.push_back(k);
                    tmp.push_back(j);
                    
                    answer.push_back(tmp);
                }
            }
        }
    }
    
    return answer;
}

Ref

https://hochoon-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B8%B0%EB%91%A5%EA%B3%BC-%EB%B3%B4-%EC%84%A4%EC%B9%98-c