[프로그래머스] 60061. 기둥과 보

문제 링크

[프로그래머스] 60061. 기둥과 보

풀이 과정

구조물 삭제가 관건인 문제였습니다.

문제의 규칙은 다음과 같습니다.

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

static boolean canBuildGidung(int x, int y, Point[][] map) {
    return x == 0 || (y - 1 >= 0 && map[x][y - 1].bo) || map[x][y].bo || (x - 1 >= 0 && map[x - 1][y].gidung);
}

canBuildGidung 메소드 는 (x, y) 좌표 위치에 기둥을 설치할 수 있는지를 판단합니다. OR 연산자를 기준으로 처음부터 1. 바닥 위에 있는지, 2. 보의 왼쪽 끝 부분 위에 있는지, 3. 보의 오른쪽 끝 부분 위에 있는지, 4. 다른 기둥 위에 있는지를 판단합니다. 네 경우 중 하나라도 가능하다면, 해당 자리에 기둥을 설치할 수 있으므로 true 를 리턴합니다.

static boolean canBuildBo(int n, int x, int y, Point[][] map) {
    return (x - 1 >= 0 && map[x - 1][y].gidung) || (x - 1 >= 0 && y + 1 <= n && map[x - 1][y + 1].gidung) || (y - 1 >= 0 && y + 1 <= n && map[x][y - 1].bo && map[x][y + 1].bo);
}

canBuildBo 메소드 는 (x, y) 좌표 위치에 보를 설치할 수 있는지를 판단합니다. OR 연산자를 기준으로 처음부터 1. 왼쪽 끝 부분이 기둥 위에 있는지, 2. 오른쪽 끝 부분이 기둥 위에 있는지, 3. 양쪽 끝 부분이 다른 보와 동시에 연결되어 있는지를 판단합니다. 세 경우 중 하나라도 가능하다면, 해당 자리에 보를 설치할 수 있으므로 true 를 리턴합니다.

static boolean canRemove(int n, Point[][] map) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (map[i][j].gidung && !canBuildGidung(i, j, map)) return false;
            if (map[i][j].bo && !canBuildBo(n, i, j, map)) return false;
        }
    }

    return true;
}

canRemove 메소드 는 해당 위치의 건축물(기둥 또는 보)를 미리 제거한 뒤, 모든 건축물들이 위 규칙을 만족하는지 확인합니다. 모든 건축물에 대해 기둥과 보 둘 중 하나라도 규칙을 만족시키지 못한다면 해당 건축물은 삭제할 수 없습니다.

코드

import java.util.ArrayList;

public class Main {
    public static ArrayList<int[]> solution(int n, int[][] build_frame) {
        Point[][] map = new Point[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                map[i][j] = new Point(false, false);
            }
        }

        for (int i = 0; i < build_frame.length; i++) {
            int x = build_frame[i][0], y = build_frame[i][1], a = build_frame[i][2], b = build_frame[i][3];

            if (b == 0) {
                if (a == 0) {
                    map[y][x].gidung = false;
                    if (!canRemove(n, map))
                        map[y][x].gidung = true;
                }

                else {
                    map[y][x].bo = false;
                    if (!canRemove(n, map))
                        map[y][x].bo = true;
                }
            }

            else {
                if (a == 0 && canBuildGidung(y, x, map)) {
                    map[y][x].gidung = true;
                }

                else if (a == 1 && canBuildBo(n, y, x, map)) {
                    map[y][x].bo = true;
                }
            }
        }

        ArrayList<int[]> answer = new ArrayList<>();
        for (int j = 0; j <= n; j++) {
            for (int i = 0; i <= n; i++) {
                if (map[i][j].gidung) answer.add(new int[]{j, i, 0});
                if (map[i][j].bo) answer.add(new int[]{j, i, 1});
            }
        }

        return answer;
    }

    static boolean canBuildGidung(int x, int y, Point[][] map) {
        return x == 0 || (y - 1 >= 0 && map[x][y - 1].bo) || map[x][y].bo || (x - 1 >= 0 && map[x - 1][y].gidung);
    }

    static boolean canBuildBo(int n, int x, int y, Point[][] map) {
        return (x - 1 >= 0 && map[x - 1][y].gidung) || (x - 1 >= 0 && y + 1 <= n && map[x - 1][y + 1].gidung) || (y - 1 >= 0 && y + 1 <= n && map[x][y - 1].bo && map[x][y + 1].bo);
    }

    static boolean canRemove(int n, Point[][] map) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (map[i][j].gidung && !canBuildGidung(i, j, map)) return false;
                if (map[i][j].bo && !canBuildBo(n, i, j, map)) return false;
            }
        }

        return true;
    }

    static class Point {
        boolean gidung, bo;

        public Point(boolean gidung, boolean bo) {
            this.gidung = gidung;
            this.bo = bo;
        }
    }

    public static void main(String[] args) {
        solution(5, new int[][]{{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}});
//        solution(5, new int[][]{{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}});
    }
}