기둥과 보 설치

2025-11-07

#JAVA#프로그래머스

3분

문제 링크

문제 풀이 시간 : 1시간 23분

문제 요약

•
2차원 격자 위에 기둥(0), 보(1) 를 설치/삭제한다.

•
설치 및 삭제는 아래 조건을 항상 만족해야만 수행된다.

•
기둥 설치 가능 조건
- ◦
  바닥 위(y == 0)
- ◦
  아래에 기둥이 있음
- ◦
  보의 한쪽 끝 위에 있음

•
보 설치 가능 조건
- ◦
  보의 한쪽 끝이 기둥 위에 있음
- ◦
  양쪽 끝이 모두 보와 연결됨

즉, 설치/삭제 이후 전체 구조물이 항상 조건을 만족해야 함.

문제 풀이

처음에는 모든 경우를 효율적으로 처리할 방법이 있는지 고민했지만,

생각보다 구조 자체가 어렵지 않다는 것을 알게 되었다.

핵심은

설치/삭제가 요청될 때마다 전체 구조물이 조건을 만족하는지만 검사하면 된다

라는 것이다.

그래서 아래 방식으로 접근했다.

핵심 아이디어

1. 자료구조

기둥과 보를 각각 boolean 2D 배열로 표현했다.

Plain text

gi[y][x] = (x,y) 위치에 기둥이 있는가?
bo[y][x] = (x,y) 위치에 보가 있는가?

2. 설치 시

각 요소를 설치할 때, 해당 구조물이 설치 가능한 조건인지 판단해서 조건을 만족하면 설치한다.

•
기둥 → giCheck(x, y)

•
보 → boCheck(x, y)

둘 중 하나라도 조건이 안 맞으면 설치하지 않는다.

3) 삭제 시

삭제 요청이 들어오면 일단 제거했다 가정한 뒤 →

구조 전체가 여전히 조건을 만족하는지 체크한다.

만약

다른 구조물이 규칙을 위반한다면 → 삭제를 취소

이 과정을 통해 “항상 유효한 상태”를 유지할 수 있다.

기둥/보 설치 조건 체크

giCheck(x, y)

기둥 설치가 가능한 경우는

•
바닥 위

•
아래에 기둥이 있음

•
아래가 보의 끝
중 하나 이상이면 가능

boCheck(x, y)

보 설치 가능 조건

•
양 끝 중 하나라도 기둥 위

•
양쪽 끝이 모두 보와 연결

둘 중 하나라도 만족하면 설치 가능

전체 유효성 검사 (

삭제 직후에는 해당 지점뿐 아니라 다른 구조물이 영향을 받았는지 확인해야 한다.

그래서 모든 기둥/보를 순회하며 각자 설치 조건을 다시 확인했다.

만약 하나라도 조건을 만족하지 않으면

→ 현재 삭제는 무효 처리

→ 되돌린다.

로직 정리

1
기둥/보 상태를 boolean 배열로 관리

2
요청을 순회하며
- •
  설치
  - ◦
    설치 가능한지 체크 → 가능하면 설치
- •
  삭제
  - ◦
    삭제 후 전체 validate → 문제 있으면 롤백

3
모든 명령이 끝나면
- •
  해당 구조물들을 리스트로 모아서 정렬 후 반환

최종 코드

Java

import java.util.*;

class Solution {
    public boolean[][] gi, bo;
    public int n;

    public boolean giCheck(int x, int y){
        if(y==0)
            return true;
        if(gi[y-1][x]==true)
            return true;
        if(x>0 && bo[y][x-1])
            return true;
        if(bo[y][x])
            return true;
        return false;
    }

    public boolean boCheck(int x, int y) {
        // 아래에 기둥
        if(y > 0 && gi[y-1][x]) return true;
        if(y > 0 && x+1 <= n && gi[y-1][x+1]) return true;

        // 양쪽 보
        if(x > 0 && x+1 <= n && bo[y][x-1] && bo[y][x+1]) return true;

        return false;
    }

    public boolean validate(int n){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                if(gi[j][i] && !giCheck(i,j)) return false;
                if(bo[j][i] && !boCheck(i,j)) return false;
            }
        }
        return true;
    }

    public int[][] solution(int n, int[][] build_frame) {
        gi = new boolean[n+1][n+1];
        bo = new boolean[n+1][n+1];
        this.n = n;

        for(int[] now : build_frame){
            int x = now[0];
            int y = now[1];
            int kind = now[2];
            int op = now[3];

            // 삭제
            if(op==0){
                if(kind == 0){
                    gi[y][x] = false;
                    if(!validate(n)) gi[y][x] = true;
                }
                else{
                    bo[y][x] = false;
                    if(!validate(n)) bo[y][x] = true;
                }
            }
            // 설치
            else{
                if(kind == 0){
                    if(giCheck(x,y)) gi[y][x] = true;
                }
                else{
                    if(boCheck(x,y)) bo[y][x] = true;
                }
            }
        }

        List<int[]> arr = new ArrayList<>();

        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                if(gi[j][i])
                    arr.add(new int[]{i,j,0});
                if(bo[j][i])
                    arr.add(new int[]{i,j,1});
            }
        }

        arr.sort((a1, a2)->{
            if(a1[0] == a2[0] && a1[1] == a2[1])
                return a1[2] - a2[2];
            if(a1[0] == a2[0])
                return a1[1] - a2[1];
            return a1[0] - a2[0];
        });

        return arr.toArray(new int[0][0]);
    }
}