[JAVA] 기둥과 보 설치( 프로그래머스 kakao 2020 공채)

 

 

 

제약 사항이 너무 많다...

 

보자마자 빡시게 구현하겠구나 생각했다.

 

이런 문제 풀 때 가장 중요한 점은 잔머리 굴리면 안된다.

 

있는 그대로 모든 조건 활용해서 구현해야 한다..

 

---

<풀이>

 

1) 격자 설정하기

 

(먼저 2차원 격자를 설정해서 문제를 풀어야 하는데 이 부분에서는 문제 내용을 어떻게 표시할지 본인만의 방법으로 생각해내야 한다.)

 

n x n 격자지만 사실은 0을 포함하고 있기 때문에 길이는 n+1 이다. 

 

기둥을 표시할 격자 gidung 과 보를 표시할 격자 boo 를 boolean 2차원 배열로 설정했다.

 

한편 문제에서 주어진 대로 (1,0) 이라는 좌표에 대해 생각해보자.

 

(1,0) 을 좌표 그대로 생각하면 x좌표가 1 이며 y좌표가 0 인점이 떠오를 것이다.

 

하지만, 이를 2차원 컴퓨터 배열로 생각하면 이야기가 달라진다. 1행의 0번째 원소이므로 우리가 흔히 생각하는 (1,0)의 좌표가 아니다. 즉 좌표가 90도 뒤집어진 형태다. 아래를 보면서 이해를 하자.

 

만약 (1,1) 이 true 라고 해보자. 이때 (1,1)은 1행 1번 원소다.

 

gidung 의 경우는 (1,1) 을 기점으로 오른쪽으로 기둥이 세워지도록 설정했다. 

boo 의 경우는 (1,1) 을 기점으로 아래로 보가 세워지도록 설정했다.

그 이유는 아래 그림을 보면 이해될 것이다.

 

 

이제 위와 같은 그림으로 생각해야 한다.

 

2) 보 설치 조건

 

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

 

위 조건에 따라 그대로 작성하면 된다.

 

만약 (x,y)에 보를 설치한다고 해보자. 빨간 기둥 2개중에 한개가 있거나 초록색 보 2개가 양쪽에 반드시 있으면 된다.

3) 기둥 설치 조건

 

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

 

(x,y) 에 기둥을 세우기 위해서는 초록색 보 2개중에 하나라도 있거나 빨간 기둥이 있거나 y==0 (바닥) 이어야 한다.

 

4) 제거 알고리즘

 

일단 제거한다.

그다음 모든 기둥과 보가 올바르게 설치되어있는지  2), 3) 의 함수를 이용해 점검한다.

만약 문제가 있다면 제거를 할 수 없으므로 원상복원 한다.

문제 없다면 넘어간다.

 

 

<전체 코드와 결과>

 

import java.util.*;

class Solution {
        static boolean[][] gidung;
        static boolean[][] boo;
        static int N;
        static Deque<int[]> ansList = new ArrayDeque<>();

        public int[][] solution(int n, int[][] build_frame) {
            N = n+1;
            gidung = new boolean[N][N]; for(int i=0;i<N;i++) gidung[i]=new boolean[N];
            boo = new boolean[N][N]; for(int i=0;i<N;i++) boo[i] = new boolean[N];

            for(int[] bf : build_frame){

                if(bf[2]==1 && bf[3]==1){ // 보 설치
                    if(booCheck(bf[0],bf[1])){
                        boo[bf[0]][bf[1]] = true;
                        ansList.add(new int[]{bf[0],bf[1],1});
                    }
                }

                if(bf[2]==0 && bf[3]==1){ // 기둥 설치
                    if(gidungCheck(bf[0],bf[1])){
                        gidung[bf[0]][bf[1]]=true;
                        ansList.add(new int[]{bf[0],bf[1],0});
                    }
                }

                if(bf[2]==0 && bf[3]==0){ // 기둥 삭제
                    gidung[bf[0]][bf[1]]=false;
                    remove(bf[0],bf[1],bf[2]);
                    if(!allCheck()){
                        gidung[bf[0]][bf[1]] = true;
                        ansList.add(new int[]{bf[0],bf[1],bf[2]});
                    }


                }
                if(bf[2]==1 && bf[3]==0){ // 보 삭제
                    boo[bf[0]][bf[1]] =false;
                    remove(bf[0],bf[1],bf[2]);
                    if(!allCheck()){
                        boo[bf[0]][bf[1]] = true;
                        ansList.add(new int[]{bf[0],bf[1],bf[2]});
                    }

                }

            }

            return ansListToAnswer();
        }

        static int[][] ansListToAnswer(){

            Iterator<int[]> iterator = ansList.iterator();
            int[][] ans = new int[ansList.size()][3];
            int i=0;
            while(iterator.hasNext()){
                ans[i++] = iterator.next();
            }
            Arrays.sort(ans,(a,b)->{
                if(a[0]!=b[0]) return a[0]-b[0];
                else if(a[1]!=b[1])return a[1]-b[1];
                else return a[2]-b[2];
            });
            return ans;
        }

        static boolean booCheck(int x, int y){
            if(y==0) return false; //바닥
            else if(gidung[x][y-1] || gidung[x+1][y-1]){ // 양쪽 기둥
                return true;
            }else if( x-1>=0 && x+1<N && boo[x-1][y] && boo[x+1][y]){ // 양쪽 보
                return true;
            }
            return false;
        }

        static boolean gidungCheck(int x,int y){
            if(y==0) return true; // 바닥
            else if((x-1>=0 && boo[x-1][y]) || boo[x][y]) return true; // 한쪽 끝에 보
            else if(y-1>=0 && gidung[x][y-1]) return true; //다른 기둥 위에

            return false;
        }

        static void remove(int x,int y,int w){
            int ansListSize = ansList.size();
            for(int i=0;i<ansListSize;i++){
                int[] tmp = ansList.pollFirst();
                if(!(tmp[0]==x && tmp[1]==y && tmp[2]==w)){
                    ansList.addLast(tmp);
                }
            }
        }

        static boolean allCheck(){
            Iterator<int[]> iterator = ansList.iterator();
            while(iterator.hasNext()){
                int[] tmp = iterator.next();
                if(tmp[2]==1){
                        if(!booCheck(tmp[0],tmp[1])) return false;

                }else{
                        if(!gidungCheck(tmp[0],tmp[1])) return false;
                }
            }
            return true;
        }

    }