(2020카카오) 기둥과 보 설치 Java

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

 

본인은 테스트케이스는 통과하는 코드를 만들었지만, 채점시 모두 틀리게 나오는 코드였다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[][] solution(int n, int[][] build_frame) {
        int[][] grid = new int[n+1][n+1];
        for(int a[] : grid) {
            Arrays.fill(a, -1);//-1로 초기화
        }

        for (int i = 0; i < build_frame.length; i++) {
            int x = build_frame[i][0];//[0] =x
            int y = build_frame[i][1];//[1] =y
            int a = build_frame[i][2];//[2] =>a 0:기둥 1:보
            int b = build_frame[i][3];//[3] =>b 0:삭제 1:설치

            if (b == 0) {//삭제하는 경우
                if(a==0){//기둥
                    //기둥위의 것이 왼쪽에 연결되어있는경우에만 지울수있음.
                    if(grid[x][y+1] != -1 && grid[x-1][y+1] ==1){
                        grid[x][y] = -1;//-1은 삭제된값
//                        System.out.println("삭제 기둥" + x+","+y);

                    }
                }else{//보
                    if((x>0&&grid[x-1][y]==1&&y>0&&grid[x][y-1]==0)||
                            x+1<n&&grid[x+1][y]!=-1&&y-1>0&&grid[x+1][y-1]==0){
                        grid[x][y] = -1;
//                        System.out.println("삭제 보" + x+","+y);

                    }
                }

            } else if (b == 1) {//설치하는 경우
                if (a == 0) {//기둥
                    //왼쪽 아래 보 _ㅣ or 아래 기둥 !
                    if (y == 0 || (x>=1 && grid[x - 1][y] == 1)|| (y>=1 && grid[x][y - 1] == 0)) {
                        grid[x][y] = 0;
//                        System.out.println(x+","+y+"ㅣ");
                    } else {
                        continue;
                    }
                } else if (a == 1) {//보
                    //왼쪽에 보 or 아래에 기둥
                    if ((x>=1 && grid[x - 1][y] != -1) || (y>=1 && grid[x][y - 1] == 0) || (x+1<=n&& y-1>0&& grid[x+1][y-1]==0 )) {
//                        System.out.println(x+","+y+"ㅡ");
                        grid[x][y] = 1;
                    } else {
                        continue;
                    }
                }
            }
        }

        Queue<Integer> x = new LinkedList<>();
        Queue<Integer> y = new LinkedList<>();
        Queue<Integer> val = new LinkedList<>();
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] != -1){
                    x.add(i);
                    y.add(j);
                    val.add(grid[i][j]);
                }
            }
        }
        int[][] answer = new int[x.size()][3];
        int size=x.size();
        for(int i=0; i<size; i++){
            answer[i][0]= x.poll();
            answer[i][1]= y.poll();
            answer[i][2]= val.poll();
//            System.out.println(answer[i][0] + "," +answer[i][1] + ": " + answer[i][2]);
        }

        return answer;
    }
}

흑흑ㅜㅜ

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

위 조건들을 이용하여 아래의 문제를 해결한다.

(1, 1)에서 오른쪽에 있는 보를 삭제하면 (2, 1)에서 오른쪽에 있는 보는 조건을 만족하지 않으므로 무시됩니다.

위와 같은 삭제를 할때의 문제 해결에 어려움이 있었다.

 

<삭제는 아래와 같이 작동한다>

우선 삭제할 위치의 구조물을 삭제한다.

 

그 후, 남아 있는 모든 구조물들을 체크하여 위의 두 규칙을 여전히 만족하는지를 판단한다.

 

삭제한 구조물은 원상복구 시키고, 하나라도 위의 규칙을 만족하지 못한다면 false를, 모든 구조물들이 만족한다면 true를 리턴한다.

 

true를 리턴 받았으면 해당 위치의 구조물을 삭제한다.

 

남아 있는 구조물들을 체크할 때 그냥 맵 전체를 탐색하며 구조물인 것을 체크

 

class Solution {
    private int n;
    private boolean[][] cols, rows; // 기둥, 보
    private final int COLUMN = 0, ROW = 1, REMOVE = 0, ADD = 1;

    public int[][] solution(int n, int[][] build_frame) {
        this.n = n;
        int count = 0;
        cols = new boolean[n + 3][n + 3];
        rows = new boolean[n + 3][n + 3];

        for (int[] frame : build_frame) {
            int x = frame[0] + 1;
            int y = frame[1] + 1;
            if (frame[2] == COLUMN) { // 기둥
                if (frame[3] == ADD && isExistCol(x, y)) { // 해당 위치에 기둥을 세울 수 있으면
                    cols[x][y] = true;
                    count++;
                }
                if (frame[3] == REMOVE && canRemove(x, y, COLUMN)) { // 삭제할 수 있으면
                    cols[x][y] = false;
                    count--;
                }
            } else { // 보
                if (frame[3] == ADD && isExistRow(x, y)) {
                    rows[x][y] = true;
                    count++;
                }
                if (frame[3] == REMOVE && canRemove(x, y, ROW)) {
                    rows[x][y] = false;
                    count--;
                }
            }
        }

        int[][] answer = new int[count][3];
        int index = 0;
        for (int i = 1; i <= n + 1; i++) { // 남아 있는 기둥과 보 배열에 저장
            for (int j = 1; j <= n + 1; j++) {
                if (cols[i][j]) answer[index++] = new int[]{i - 1, j - 1, COLUMN};
                if (rows[i][j]) answer[index++] = new int[]{i - 1, j - 1, ROW};
            }
        }
        return answer;
    }

    private boolean isExistCol(int x, int y) { // x, y 위치에 존재할 수 있는지
        return y == 1 || cols[x][y - 1] || rows[x][y] || rows[x - 1][y];
    }

    private boolean isExistRow(int x, int y) {
        return cols[x][y - 1] || cols[x + 1][y - 1] || (rows[x - 1][y] && rows[x + 1][y]);
    }

    private boolean canRemove(int x, int y, int type) {
        boolean result = true;

        if (type == COLUMN) cols[x][y] = false; // 임시로 삭제
        else rows[x][y] = false;

        loop:
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (cols[i][j] && !isExistCol(i, j)) {
                    result = false;
                    break loop;
                }
                if (rows[i][j] && !isExistRow(i, j)) {
                    result = false;
                    break loop;
                }
            }
        }

        if (type == COLUMN) cols[x][y] = true; // 삭제했던 구조물 원상복구
        else rows[x][y] = true;

        return result;
    }
}

 

 

제1출처 : leveloper.tistory.com/100

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