알고리즘) 카카오 블라인드 채용 2020, 기둥과 보 설치

Kakao Blind Recruitment 2020

기둥과 보 설치

프로그래머스

 

 

풀이

주목할 점

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

벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.
바닥에 보를 설치 하는 경우는 없습니다.
구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다.
구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않습니다.

위의 조건에 따라 코드를 짜봤다. 우선 기둥이 만들어질 수 있는 조건을 살펴보면, 아래와 같다.

 

1. 바닥 위에 있는 경우

2. 보의 한쪽 끝 부분 위에 있는 경우(기둥이 설치될 좌표나 좌측 좌표에 보가 있다면 가능)

3. 다른 기둥 위에 있는 경우(아래쪽 좌표에 기둥이 있는 경우)

 

주어진 n의 맵 안에서 이루어지며, 바닥에 보를 설치하는 등 이상한 예외의 상황이 주어지지 않는다는 것이다.

위의 조건에 따라 코드를 짜봤지만, 정확성 6번 7번을 제외하고는 다 틀리니..... 오늘은 도저히 모르겠어서 일단 포스팅을 해두고 다시 풀어야겠다.

 

---

다시 본 결과 너무 어이없는 실수를 했던거였다.. 우선 결과 값을 저장하는 부분에서 기둥과 보가 같은 좌표에 동시에 존재할 수 있는데, else if를 통해 기둥 or 보를 저장했으니 답이 맞을리가 없었다.. 그래서 이 부분을 고쳐줬다. (getResult 메소드 부분)
그리고 손 본곳은 삭제 부분이다. 기둥과 보 조건에 따라서 주변 체크는 해줘놓고, 그 건설물에 대해 존재할 수 있는 조건을 체크 안해줬었다.. 이렇게 수정하니 너무 간단하게 정답이 되는 코드였다.. 

결론 : 힘들어도 꼼곰하게.. 막히면 처음부터 !!

 

코드

public class ColumnAndBeam_2019 {
    static int[][][] map;
    final static int COLUMN =0, BEAM =1, ADD =1, REMOVE =0;
    private static int[][] solution(int n, int[][] build_frame) {
        initMap(n);
        int cnt =0;
        for(int[] cmd : build_frame) {
            // 0 : x
            // 1 : y
            // 2 : 종류 (0 : 기둥 or 1 : 보)
            // 3 : 삭제 or 생성(0: 삭제, 1: 생성)
            cnt = doCmd(cmd, cnt);
        }
        for(int y=0; y<=n+1; y++) {
            for(int x=0; x<=n+1; x++) {
                if(map[y][x][COLUMN] ==1) {
                    System.out.print(COLUMN + " ");
                }else if(map[y][x][BEAM] ==1) {
                    System.out.print(BEAM + " ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }

        return getResult(n,cnt);
    }

    private static int[][] getResult(int n, int cnt) {
        int[][] result = new int[cnt][];
        int idx=0;
        for(int x=1; x<=n+1; x++) {
            for(int y=1; y<=n+1; y++) {
                if(map[y][x][COLUMN] ==1) {
                    int[] tmp = {x-1,y-1, COLUMN};
                    result[idx++] = tmp;
                } else if(map[y][x][BEAM] ==1) {
                    int[] tmp = {x-1,y-1, BEAM};
                    result[idx++] = tmp;
                }
            }
        }
        return result;
    }

    private static void initMap(int n) {
        map = new int[n+3][n+3][2];
    }

    private static int doCmd(int[] cmd, int cnt) {
        int x = cmd[0] +1;
        int y = cmd[1] +1;

        if(cmd[3] ==REMOVE) {    // 삭제
            if(cmd[2] == COLUMN) {  // 기둥
                if(canRemoveColumn(x,y)) {
                    map[y][x][COLUMN] = 0;
                    cnt--;
                }
            } else {    //  보
                if(canRemoveBeam(x,y)) {
                    map[y][x][BEAM] = 0;
                    cnt--;
                }
            }
        } else {    // 생성
            if(cmd[2] == COLUMN) {   // 기둥
                if(canMakeColumn(x,y)) {
                    map[y][x][COLUMN] = 1;
                    cnt++;
                }
            } else {    // 보
                if(canMakeBeam(x,y)) {
                    map[y][x][BEAM] = 1;
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private static boolean canMakeBeam(int x, int y) { // 보
        boolean result = false;
        if(map[y-1][x][COLUMN] == 1 || map[y-1][x+1][COLUMN] ==1) { // 한쪽 끝 부분이 기둥 위에 있거나,
            result = true;
        }
        if(map[y][x-1][BEAM] == 1 && map[y][x+1][BEAM] ==1) {    // 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
            result = true;
        }

        return result;
    }

    private static boolean canMakeColumn(int x, int y) { // 기둥
        boolean result = false;
        if(y == 1) {     // 바닥 위에 있거나
            result = true;
        }
        if(map[y][x][BEAM] ==1 || (map[y][x-1][BEAM] ==1)) { // 보의 한쪽 끝 부분 위에 있거나
            result = true;
        }
        if(map[y-1][x][COLUMN] == 1) {  // 또는 다른 기둥 위에 있어야 합니다.
            result = true;
        }
        return result;
    }

    private static boolean canRemoveColumn(int x, int y) {
        boolean result = true;
        if(map[y][x][COLUMN] ==1) {
            map[y][x][COLUMN] = 0;
            if (map[y+1][x][COLUMN] == 1) {  // 위에 기둥이 있는 경우
                if (!canMakeColumn(x, y + 1)) {
                    result = false;
                }
            } else if (map[y+1][x][BEAM] == 1) { // 위에 보가 있는 경우
                if (!canMakeBeam(x, y + 1)) {
                    result = false;
                }
            }
            if (map[y+1][x-1][BEAM] == 1) { // 좌측 상단에 보가 있는 경우
                if (!canMakeBeam(x - 1, y + 1)) {
                    result = false;
                }
            }
            map[y][x][COLUMN] = 1;
        }
        return result;
    }

    private static boolean canRemoveBeam(int x, int y) {
        map[y][x][BEAM] =0;
        boolean result = true;

        if(map[y][x][COLUMN] ==1 || map[y][x+1][COLUMN] == 1) {   // 보의 양 끝에 기둥이 있는 경우
            result = false;
        }
        if(map[y][x-1][BEAM] == 1 || map[y][x+1][BEAM] ==1) {    // 양 옆에 보가 있는 경우
            result = false;
        }

        map[y][x][BEAM] = 1;
        return result;
    }


    public static void main(String[] args) {
        int n = 5;
//        int[][] build_frame = {{1,0,0,1},{1,1,1,1},{2,1,0,1},{2,2,1,1},{5,0,0,1},{5,1,0,1},{4,2,1,1},{3,2,1,1}};
        int[][] build_frame = {{0,0,0,1},{2,0,0,1},{4,0,0,1},{0,1,1,1},{1,1,1,1},{2,1,1,1},{3,1,1,1},{2,0,0,0},{1,1,1,0},{2,2,0,1}};
        int[][] result = solution(n, build_frame);

        for(int[] pos : result) {
            System.out.println(pos[0] + ", " + pos[1] +", " +pos[2]);
        }
    }
}

---

코드2

public class ColumnAndBeam_2019 {
    static int[][][] map;
    final static int COLUMN =0, BEAM =1, ADD =1, REMOVE =0;
    private static int[][] solution(int n, int[][] build_frame) {
        initMap(n);
        int cnt =0;
        for(int[] cmd : build_frame) {
            // 0 : x
            // 1 : y
            // 2 : 종류 (0 : 기둥 or 1 : 보)
            // 3 : 삭제 or 생성(0: 삭제, 1: 생성)
            cnt = doCmd(cmd, cnt);
        }
        print(n); // 답과 무관하게 확인하기 위해 쓴 코드입니다

        return getResult(n,cnt);
    }

    private static int[][] getResult(int n, int cnt) {
        int[][] result = new int[cnt][];
        int idx=0;
        for(int x=1; x<=n+1; x++) {
            for(int y=1; y<=n+1; y++) {
                if(map[x][y][COLUMN] ==1) {
                    int[] tmp = {x-1,y-1, COLUMN};
                    result[idx++] = tmp;
                }
                if(map[x][y][BEAM] ==1) {
                    int[] tmp = {x-1,y-1, BEAM};
                    result[idx++] = tmp;
                }
            }
        }
        return result;
    }

    private static void initMap(int n) {
        map = new int[n+3][n+3][2];
    }

    private static int doCmd(int[] cmd, int cnt) {
        int x = cmd[0] +1;
        int y = cmd[1] +1;

        if(cmd[3] ==REMOVE) {    // 삭제
            if(cmd[2] == COLUMN) {  // 기둥
                if(canRemoveColumn(x,y)) {
                    map[x][y][COLUMN] = 0;
                    cnt--;
                }
            } else {    //  보
                if(canRemoveBeam(x,y)) {
                    map[x][y][BEAM] = 0;
                    cnt--;
                }
            }
        } else {    // 생성
            if(cmd[2] == COLUMN) {   // 기둥
                if(canMakeColumn(x,y)) {
                    map[x][y][COLUMN] = 1;
                    cnt++;
                }
            } else {    // 보
                if(canMakeBeam(x,y)) {
                    map[x][y][BEAM] = 1;
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private static boolean canMakeBeam(int x, int y) { // 보
        boolean result = false;
        if(map[x][y-1][COLUMN] == 1 || map[x+1][y-1][COLUMN] ==1) { // 한쪽 끝 부분이 기둥 위에 있거나,
            result = true;
        }
        if(map[x-1][y][BEAM] == 1 && map[x+1][y][BEAM] ==1) {    // 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
            result = true;
        }

        return result;
    }

    private static boolean canMakeColumn(int x, int y) { // 기둥
        boolean result = false;
        if(y == 1) {     // 바닥 위에 있거나
            result = true;
        }
        if(map[x][y][BEAM] ==1 || (map[x-1][y][BEAM] ==1)) { // 보의 한쪽 끝 부분 위에 있거나
            result = true;
        }
        if(map[x][y-1][COLUMN] == 1) {  // 또는 다른 기둥 위에 있어야 합니다.
            result = true;
        }
        return result;
    }

    private static boolean canRemoveColumn(int x, int y) {
        boolean result = true;
        if(map[x][y][COLUMN] ==1) {
            map[x][y][COLUMN] = 0;
            if (map[x][y+1][COLUMN] == 1 && !canMakeColumn(x, y + 1)) {  // 위에 기둥이 있는 경우
                result = false;
            } if (map[x][y+1][BEAM] == 1 && !canMakeBeam(x, y + 1)) { // 위에 보가 있는 경우
                result = false;
            }
            if (map[x-1][y+1][BEAM] == 1 && !canMakeBeam(x - 1, y + 1)) { // 좌측 상단에 보가 있는 경우
                result = false;
            }
            map[x][y][COLUMN] = 1;
        }
        return result;
    }

    private static boolean canRemoveBeam(int x, int y) {
        map[x][y][BEAM] =0;
        boolean result = true;

        if( (map[x][y][COLUMN] ==1 && !canMakeColumn(x,y))|| (map[x+1][y][COLUMN] == 1) && !canMakeColumn(x+1,y)) {   // 보의 양 끝에 기둥이 있는 경우
            result = false;
        }
        if( (map[x-1][y][BEAM] == 1 && !canMakeBeam(x-1,y)) || (map[x+1][y][BEAM] ==1) && !canMakeBeam(x+1,y)) {    // 양 옆에 보가 있는 경우
            result = false;
        }

        map[x][y][BEAM] = 1;
        return result;
    }

    private static void print(int n) { // 편의를 위한 프린트 함수
        for(int y=0; y<=n+1; y++) {
            for(int x=0; x<=n+1; x++) {
                if(map[x][y][COLUMN] ==1) {
                    System.out.print(COLUMN + " ");
//                    System.out.print("| ");
                }else if(map[x][y][BEAM] ==1) {
                    System.out.print(BEAM + " ");
//                    System.out.print("- ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        int n = 5;
//        int[][] build_frame = {{1,0,0,1},{1,1,1,1},{2,1,0,1},{2,2,1,1},{5,0,0,1},{5,1,0,1},{4,2,1,1},{3,2,1,1}};
        int[][] build_frame = {{0,0,0,1},{2,0,0,1},{4,0,0,1},{0,1,1,1},{1,1,1,1},{2,1,1,1},{3,1,1,1},{2,0,0,0},{1,1,1,0},{2,2,0,1}};
        int[][] result = solution(n, build_frame);

        for(int[] pos : result) {
            System.out.println(pos[0] + ", " + pos[1] +", " +pos[2]);
        }
    }
}