골드에그

1. 문제요약

코딩테스트 연습 - 기둥과 보 설치 | 프로그래머스 스쿨 (programmers.co.kr)

n x n 크기의 2차원 벽면에 기둥(세로) 와 보(가로) 를 설치해 구조물을 만들려고 한다.

벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame 이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성하라.

룰은 다음과 같다.

① 기둥과 보는 1 X 1 크기의 격자이다. 격자 칸의 각 변에 정확히 일치하도록 설치하여야 한다.

② 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.

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

2. 문제예제

3. 팩트추출

Fact 1 : 한 지점에서 기둥과 보를 같이 설치/해제할 수 있으므로, map 2차원 배열에 기둥과 보에 대한 정보를 같이 삽입할 수 없다. 기둥의 설치 여부를 나타내는 map 하나와 보의 설치 여부를 나타내는 map 하나를 각각 준비해야 한다.

Fact 2 : 위 문제예제에서도 살펴보았듯이 명령어를 순서대로 적용할 때 실시간으로 가능 여부를 체크해야 한다.

4. 문제전략

문제전략이라고 할 것이 없다. 명령어를 하나씩 받고 아래 2번 3번 룰에 어긋나지 않는지만 체크하면 된다.

② 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.

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

5. 소스코드

class Solution {
    static int N;
    static boolean[][] column;
    static boolean[][] row;

    public enum materialType {
        COLUMN(0), ROW(1);
        private final int indexNumber;
        materialType(int i) { this.indexNumber = i; }
        public int getIndex() { return indexNumber; }
    };

    public enum constructType {
        DESTRUCT(0), CONSTRUCT(1);
        private final int indexNumber;
        constructType(int i) { this.indexNumber = i; }
        public int getIndex() { return indexNumber; }
    };
    public int[][] solution(int n, int[][] build_frame) {
        int structureCount = 0;
        N = n;
        column = new boolean[n + 2][n + 2];
        row = new boolean[n + 2][n + 2];

        for(int[] frame : build_frame){
            int x = frame[0] + 1;
            int y = frame[1] + 1;
            int structureType = frame[2];
            int commandType = frame[3];

            if(commandType == constructType.CONSTRUCT.getIndex()){
                if(structureType == materialType.COLUMN.getIndex() && checkColumn(x, y)){
                    column[x][y] = true;
                    structureCount++;
                }
                if(structureType == materialType.ROW.getIndex() && checkRow(x, y)){
                    row[x][y] = true;
                    structureCount++;
                }
            } else if(commandType == constructType.DESTRUCT.getIndex()){
                if(structureType == materialType.COLUMN.getIndex()){
                    column[x][y] = false;
                } else if(structureType == materialType.ROW.getIndex()) {
                    row[x][y] = false;
                }
                if(canDestruct(x, y)) {
                    structureCount--;
                    continue;
                }
                if(structureType == materialType.COLUMN.getIndex()){
                    column[x][y] = true;
                } else if(structureType == materialType.ROW.getIndex()) {
                    row[x][y] = true;
                }
            }
        }

        int index = 0;
        int[][] answer = new int[structureCount][3];

        for(int i = 1 ; i <= n + 1 ; ++i){
            for(int j = 1 ; j <= n + 1 ; ++j){
                if(column[i][j]) answer[index++] = new int[]{i - 1, j - 1, materialType.COLUMN.getIndex()};
                if(row[i][j]) answer[index++] = new int[]{i - 1, j - 1, materialType.ROW.getIndex()};
            }
        }
        return answer;
    }
    private boolean checkColumn(int x, int y) {
        return y == 1 || column[x][y - 1] || row[x - 1][y] || row[x][y];
    }

    private boolean checkRow(int x, int y) {
        return column[x][y - 1] || column[x + 1][y - 1] || (row[x - 1][y] && row[x + 1][y]);
    }

    private boolean canDestruct(int x, int y) {
        for(int i = 1 ; i <= N + 1 ; ++i){
            for(int j = 1 ; j <= N + 1 ; ++j){
                if(column[i][j] && !checkColumn(i, j)){
                    return false;
                }
                if(row[i][j] && !checkRow(i, j)){
                    return false;
                }
            }
        }
        return true;
    }
}