Lv 3. 기둥과 보

 

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

프로그래머스

 

 

 

📌 자바(Java)로 푸는 기둥과 보 설치 문제 풀이 🚀

---

🔎 문제 개요

이 문제는 프로그래머스 - 기둥과 보 설치 문제입니다.
주어진 명령에 따라 기둥과 보를 설치하거나 삭제해야 합니다.
설치 조건을 만족하는 경우만 설치할 수 있으며, 삭제 후에도 구조물이 유지되는 경우만 삭제 가능합니다.

---

💡 예제 입력

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}
};

💡 예제 출력

[[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 구조물 유효성 검증 + 시뮬레이션을 활용합니다.

✏️ 주요 고려 사항

✔ 기둥과 보의 설치 조건을 만족해야만 설치 가능
✔ 삭제 후에도 전체 구조가 유지되는 경우만 삭제 가능
✔ 기둥과 보는 2차원 배열(pillars[][], beams[][])로 관리
✔ 삭제 가능 여부를 검증하는 canDelete() 함수 필요

---

🔹 Java 코드 해설

class Solution {

    boolean[][] pillars;  // 기둥 존재 여부
    boolean[][] beams;    // 보 존재 여부
    int count = 0;        // 설치된 구조물 개수

    public int[][] solution(int n, int[][] build_frame) {
        pillars = new boolean[n + 1][n + 1];
        beams = new boolean[n + 1][n + 1];

        for (int[] order : build_frame) {
            int x = order[0];
            int y = order[1];
            int type = order[2];  // 0: 기둥, 1: 보
            int action = order[3]; // 0: 삭제, 1: 설치

            if (type == 0) { // 기둥
                if (action == 1) {
                    if (isValidPillar(x, y)) {
                        pillars[x][y] = true;
                        count++;
                    }
                } else {
                    pillars[x][y] = false;
                    if (!canDelete(n)) pillars[x][y] = true;
                    else count--;
                }
            } else { // 보
                if (action == 1) {
                    if (isValidBeam(x, y)) {
                        beams[x][y] = true;
                        count++;
                    }
                } else {
                    beams[x][y] = false;
                    if (!canDelete(n)) beams[x][y] = true;
                    else count--;
                }
            }
        }

        int[][] answer = new int[count][3];
        int idx = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (pillars[i][j]) {
                    answer[idx][0] = i;
                    answer[idx][1] = j;
                    answer[idx++][2] = 0;
                }
                if (beams[i][j]) {
                    answer[idx][0] = i;
                    answer[idx][1] = j;
                    answer[idx++][2] = 1;
                }
            }
        }
        return answer;
    }

    // 삭제 가능 여부 확인
    public boolean canDelete(int n) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (beams[i][j] && !isValidBeam(i, j)) return false;
                if (pillars[i][j] && !isValidPillar(i, j)) return false;
            }
        }
        return true;
    }

    // 기둥 유효성 검증
    public boolean isValidPillar(int x, int y) {
        if (y == 0) return true; // 바닥 위
        else if (y > 0 && pillars[x][y - 1]) return true; // 아래에 기둥이 있음
        else if (x > 0 && beams[x - 1][y] || beams[x][y]) return true; // 보 위
        return false;
    }

    // 보 유효성 검증
    public boolean isValidBeam(int x, int y) {
        if (y > 0 && (pillars[x][y - 1] || pillars[x + 1][y - 1])) return true; // 한쪽 끝이 기둥 위
        else if (x > 0 && beams[x - 1][y] && beams[x + 1][y]) return true; // 양쪽 끝이 다른 보와 연결
        return false;
    }
}

---

🔍 코드 설명

📌 1. 구조물 설치 및 삭제 처리

for (int[] order : build_frame) {
    int x = order[0];
    int y = order[1];
    int type = order[2];  // 0: 기둥, 1: 보
    int action = order[3]; // 0: 삭제, 1: 설치

• type == 0 → 기둥
• type == 1 → 보
• action == 1 → 설치
• action == 0 → 삭제

---

📌 2. 기둥 설치 조건

if (y == 0) return true; // 바닥 위
else if (y > 0 && pillars[x][y - 1]) return true; // 아래에 기둥이 있음
else if (x > 0 && beams[x - 1][y] || beams[x][y]) return true; // 보 위
return false;

✔ 기둥은 바닥 위, 다른 기둥 위, 보의 끝 부분 위에 설치 가능

---

📌 3. 보 설치 조건

if (y > 0 && (pillars[x][y - 1] || pillars[x + 1][y - 1])) return true; // 한쪽 끝이 기둥 위
else if (x > 0 && beams[x - 1][y] && beams[x + 1][y]) return true; // 양쪽 끝이 다른 보와 연결
return false;

✔ 보는 한쪽 끝이 기둥 위, 혹은 양쪽 끝이 보와 연결되어야 설치 가능

---

📌 4. 삭제 가능 여부 확인

for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
        if (beams[i][j] && !isValidBeam(i, j)) return false;
        if (pillars[i][j] && !isValidPillar(i, j)) return false;
    }
}
return true;

✔ 삭제 후에도 모든 구조물이 유효한 경우에만 삭제 가능

---

🔥 시간 복잡도 분석

연산	최악의 경우 수행 횟수	시간 복잡도
for 루프 (설치/삭제 처리)	n^2	O(n^2)
canDelete() (모든 구조물 검사)	n^2	O(n^2)
총합		O(n^3)

✅ 최대 1000번 연산으로 제한 내 해결 가능

---

🏆 정리

✅ 핵심 포인트

✔ 설치 및 삭제 시 유효성 검증 필요
✔ 삭제 후에도 구조물이 유지되는지 확인 필요
✔ O(n^3) 내에서 효율적으로 해결 가능

---

문제를 접했을 때 상당히 많은 글씨와 설명에 머리가 아팠고, 기둥과 보의 방향이 정해져있다는 것을 나중에서야 깨달아 방향처리를 어떻게해야할지 혼자 머리를 아프게 쥐싸맸던 문제입니다.  방향이 정해져 있기 때문에 boolean[][] 2차원 배열 2개로 위치를 파악할 수 있게 되더라구요.

문제를 어렵게 바라보는 습관을 고쳐야겠네요.. ㅎㅎ

 

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다!