2020 - 기둥과 보 설치

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

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

[ 문제풀이 ]

별다른 알고리즘 필요 없이 주어진 조건대로 구현하면 되는 문제지만 생각보다 해결하는데 상당히 시간이 많이 소요되었다.

​기둥과 보를 어떻게 관리할 것인지가 가장 까다로운 부분이다. 기둥과 보를 다음과 같이 2차원 좌표로 관리하였다. 한 배열에다 관리하는 것보다 각각 나눠서 2개의 배열로 관리하는 것이 편하다.

기둥과 보를 관리하는 방법을 해결하였기 때문에 남은 것은 기둥과 보를 제거했을 상황이다.

​기둥과 보를 제거했을 때 영향을 미치는 범위는 위쪽뿐이다. 왜냐하면 주어진 입력이 범위를 벗어나거나 겹쳐지는 등 불가능한 입력은 주어지지 않기 때문에 아래쪽 부분은 현재의 기둥과 보가 생성되기 전에 이미 생성된 친구들이다.

​먼저 기둥을 제거했을때 영향을 미치는 범위는 기둥을 통해 기둥과 보가 생성될 수 있는 조건이다.

• 기둥은 기둥 위에 생성될 수 있기 때문에 제거한 기둥 위쪽에 기둥이 존재하는 경우
• 보는 기둥 위에 생성될 수 있기 때문에 제거한 기둥 위쪽에 양쪽으로 보가 존재하는 경우

다음으로 보를 제거했을 때 영향을 미치는 범위는 보를 통해 기둥과 보가 생성될 수 있는 조건이다.

• 기둥은 보의 한쪽 끝부분에 생성될 수 있기 때문에 제거한 보의 양쪽으로 기둥이 존재하는 경우
• 보는 양쪽 끝으로 보와 연결되어야 생성될 수 있기 때문에 양쪽으로 보가 존재하는 경우

class Solution {
    boolean[][] column, beam;
    
    public int[][] solution(int n, int[][] build_frame) {
        column = new boolean[n + 1][n + 1];
        beam = new boolean[n + 1][n + 1];
        
        int count = 0; //기둥과 보의 개수
        for (int[] node : build_frame) {
            int x = node[0];
            int y = node[1];
            int a = node[2];
            int b = node[3];
            
            if (a == 0) {
                //기둥 제거
                if (b == 0) {
                    column[y][x] = false;
                    if (deleteColumn(n, y, x)) {
                        count--;
                        continue;
                    }
                    column[y][x] = true;
                } 
                //기둥 생성
                else {
                    if (createColumn(y, x)) {
                        column[y][x] = true;
                        count++;
                    }
                }
            } else {
                //보 제거
                if (b == 0) {
                    beam[y][x] = false;
                    if (deleteBeam(n, y, x)) {
                        count--;
                        continue;
                    }
                    beam[y][x] = true;
                }
                //보 생성
                else {
                    if (createBeam(n, y, x)) {
                        beam[y][x] = true;
                        count++;
                    }
                }
            }
        }
        
        int[][] answer = new int[count][3];
        int idx = 0;
        //1.x, 2.y 순으로 정렬해야하기 때문에
        for (int j = 0; j <= n; ++j) {
            for (int i = 0; i <= n; ++i) {
                //1.기둥, 2.보 순으로 정렬해야하기 때문에
                if (column[i][j]) {
                    answer[idx][0] = j;
                    answer[idx][1] = i;
                    answer[idx++][2] = 0;
                }
                
                if (beam[i][j]) {
                    answer[idx][0] = j;
                    answer[idx][1] = i;
                    answer[idx++][2] = 1;
                }
                
                if (idx == count) return answer;
            }
        }
        
        return null;
    }
    
    public boolean createColumn(int y, int x) {
        //바닥 위에 있거나, 다른 기둥 위에 있는 경우
        if (y == 0 || column[y - 1][x]) return true;
        //보의 한쪽 끝 부분 위에 있는 경우
        if ((x > 0 && beam[y][x - 1]) || beam[y][x]) return true;
        
        return false;
    }
    
    public boolean createBeam(int n, int y, int x) {
        //한쪽 끝 부분이 기둥인 경우
        if ((y > 0 && column[y - 1][x]) || (y > 0 && x < n && column[y - 1][x + 1])) return true;
        //양쪽 끝이 보인 경우
        if ((x > 0 && x < n) && (beam[y][x - 1] && beam[y][x + 1])) return true;
        
        return false;
    }
    
    public boolean deleteColumn(int n, int y, int x) {
        //위에 기둥이 존재하는 경우
        if (y < n && column[y + 1][x]) {
            if (!createColumn(y + 1, x)) return false;
        }
        //왼쪽 위에 보가 존재하는 경우
        if ((y < n && x > 0) && beam[y + 1][x - 1]) {
            if (!createBeam(n, y + 1, x - 1)) return false;
        }
        //위에 보가 존재한는 경우 
        if (y < n && beam[y + 1][x]) {
            if (!createBeam(n, y + 1, x)) return false;
        }
        
        return true;
    }
    
    public boolean deleteBeam(int n, int y, int x) {
        //현재 위치에 기둥이 존재하는 경우
        if (column[y][x]) {
            if (!createColumn(y, x)) return false;
        }
        //오른쪽에 기둥이 존재하는 경우
        if (x < n && column[y][x + 1]) {
            if (!createColumn(y, x + 1)) return false;
        }
        //왼쪽에 보가 존재하는 경우
        if (x > 0 && beam[y][x - 1]) {
            if (!createBeam(n, y, x - 1)) return false;
        }
        //오른쪽에 보가 존재하는 경우
        if (x < n && beam[y][x + 1]) {
            if (!createBeam(n, y, x + 1)) return false;
        }
        return true;
    }
}