[프로그래머스] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT/Level 3)

문제 📃

문제 링크

n x n 크기의 격자 형태의 벽면이 존재하고, 각 격자는 1 x 1크기이다.
이 벽면에 기둥과 보를 설치하여 구조물을 만드는데 격자의 각 변에 정확히 일치하게 설치할 수 있다. 🏛

기둥과 보는 길이가 1인 선분으로 표현할 수 있고 다음과 같은 규칙을 가지고 있다.

기둥

• 바닥 위에 있거나
• 보의 한쪽 끝 부분 위에 있거나
• 다른 기둥 위에 있거나

보자기

• 한쪽 끝 부분이 기둥 위에 있거나
• 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.

기둥과 보를 설치하거나 삭제하는 명령이 주어지는데 그 과정에서 남은 기둥과 보들이 위의 규칙을 만족하지 못한다면 해당 작업은 취소한다.
이 때 주어진 모든 명령을 수행한 후 구조물의 상태를 반환하는 문제이다.

풀이 ✏️

별다른 알고리즘 없이 시뮬레이션으로 푸는 문제였다.

1. 명령에 따라 기둥이나 보를 삭제하거나 설치한다.
2. 제대로 삭제 혹은 설치 되었는지 확인한다
3. 제대로 삭제 혹은 설치 되지 않은 경우 복구한다.

처음엔 되게 쉽게 느껴졌는데 일단 좌표를 주어진 숫자대로 활용하려면 벽의 위아래를 뒤집어서 생각해야했고
나는 좌표를 arr[x][y]의 형태로 생각하고 푸는게 편한데 여긴 반대로 주어졌고
주어진 조건이 격자라서, 배열로 해결하려면 n의 크기를 한 칸 늘려줘야 했다
이 세 가지 때문에 엄청 헷갈렸다

아무튼 그리고 삭제했을 경우를 인접한 칸만 확인해보면 된다고 생각해서 삭제한 칸의 사방만 확인해줬는데, 보자기와 기둥이 상하좌우 1칸씩 뻗는 구조라서 대각선까지 확인해줘야 하는 걸 간과해서 틀렸었다. 그 외에는 조건만 잘 확인하면 되는 문제였다.

코드 💻

public class Solution {
    int[][][] wall;
    int n;
    public int[][] solution(int n, int[][] build_frame) {
        int[][] answer = {};
        wall = new int[n+1][n+1][2];
        this.n = n+1;
        int cnt = 0;
        for(int[] build : build_frame) {
            int y = build[0];
            int x = build[1];
            int a = build[2];
            int cmd = build[3];

            // 설치 or 삭제
            wall[x][y][a] = cmd;
            cnt = cmd==1 ? cnt+1 : cnt-1;

            // 복구
            if(cmd == 1) {
                if(!isRightAdd(x,y,a)) {
                    wall[x][y][a] = 0;
                    cnt--;
                }
            }
            else if(cmd == 0) {
                if(!isRightRemove(x,y,a)) {
                    wall[x][y][a] = 1;
                    cnt++;
                }
            }
        }
        answer = new int[cnt][3];
        int idx = 0;
        for(int i=0;i<this.n;i++) {
            for(int j=0;j<this.n;j++) {
                for(int k=0; k<2; k++)
                    if(wall[j][i][k] == 1)
                        answer[idx++] = new int[]{i,j,k};
            }
        }
        return answer;
    }
    boolean isRightAdd(int x, int y, int a) {
        // 기둥일 경우
        if(a == 0) {
            // 바닥에 세운 경우
            if(x == 0)
                return true;
            //기둥위에 세운 경우
            if(wall[x-1][y][0] == 1)
                return true;
            // 보 위에 세운 경우
            if(wall[x][y][1] == 1 || (y > 0 && wall[x][y-1][1] == 1))
                return true;
        }
        // 보인 경우
        if(a == 1) {
            // 기둥 위에 세운 경우
            if(wall[x-1][y][0] == 1 || (y < n - 1 && wall[x-1][y+1][0] == 1))
                return true;
            // 양쪽 끝이 보인 경우
            if((y > 0 && wall[x][y-1][1] == 1) && (y < n - 1 && wall[x][y+1][1] == 1))
                return true;
        }
        return false;
    }
    boolean isValid(int x,int y){
        return 0<=x && x<n && 0<=y && y<=n;
    }
    boolean isRightRemove(int x,int y,int a) {
    	// 삭제한거 주변 구조물들 다 제대로 설치된건지 확인
        int[] dx = {1,1,-1,-1,1,0,-1,0,0};
        int[] dy = {-1,1,-1,1,0,1,0,-1,0};
        for(int i=0; i<9; i++) {
            int nxtx = x + dx[i];
            int nxty = y + dy[i];
            if(isValid(nxtx,nxty)) {
                if(wall[nxtx][nxty][0] == 1) {
                    if(!isRightAdd(nxtx, nxty, 0))
                        return false;
                }
                if(wall[nxtx][nxty][1] == 1) {
                    if(!isRightAdd(nxtx, nxty, 1))
                        return false;
                }
            }
        }
        return true;
    }
}