기둥과 보 설치
문제 풀이 시간 : 1시간 23분
문제 요약
- 2차원 격자 위에 기둥(0), 보(1) 를 설치/삭제한다.
- 설치 및 삭제는 아래 조건을 항상 만족해야만 수행된다.
- 기둥 설치 가능 조건
- 보 설치 가능 조건
즉, 설치/삭제 이후 전체 구조물이 항상 조건을 만족해야 함.
문제 풀이
처음에는 모든 경우를 효율적으로 처리할 방법이 있는지 고민했지만,
생각보다 구조 자체가 어렵지 않다는 것을 알게 되었다.
핵심은
설치/삭제가 요청될 때마다 전체 구조물이 조건을 만족하는지만 검사하면 된다
라는 것이다.
그래서 아래 방식으로 접근했다.
핵심 아이디어
1. 자료구조
기둥과 보를 각각 boolean 2D 배열로 표현했다.
gi[y][x] = (x,y) 위치에 기둥이 있는가?
bo[y][x] = (x,y) 위치에 보가 있는가?2. 설치 시
각 요소를 설치할 때, 해당 구조물이 설치 가능한 조건인지 판단해서 조건을 만족하면 설치한다.
- 기둥 →
giCheck(x, y) - 보 →
boCheck(x, y)
둘 중 하나라도 조건이 안 맞으면 설치하지 않는다.
3) 삭제 시
삭제 요청이 들어오면 일단 제거했다 가정한 뒤 →
구조 전체가 여전히 조건을 만족하는지 체크한다.
만약
다른 구조물이 규칙을 위반한다면 → 삭제를 취소
이 과정을 통해 “항상 유효한 상태”를 유지할 수 있다.
기둥/보 설치 조건 체크
giCheck(x, y) → 기둥 설치 가능 여부
기둥 설치가 가능한 경우는
- 바닥 위
- 아래에 기둥이 있음
- 아래가 보의 끝
boCheck(x, y) → 보 설치 가능 여부
보 설치 가능 조건
- 양 끝 중 하나라도 기둥 위
- 양쪽 끝이 모두 보와 연결
둘 중 하나라도 만족하면 설치 가능
전체 유효성 검사 (validate())
삭제 직후에는 해당 지점뿐 아니라 다른 구조물이 영향을 받았는지 확인해야 한다.
그래서 모든 기둥/보를 순회하며 각자 설치 조건을 다시 확인했다.
만약 하나라도 조건을 만족하지 않으면
→ 현재 삭제는 무효 처리
→ 되돌린다.
로직 정리
- 기둥/보 상태를 boolean 배열로 관리
- 요청을 순회하며
- 모든 명령이 끝나면
최종 코드
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]);
}
}
함께 읽으면 좋은 글
택배상자
order 배열은 택배 기사님이 원하는 상자 적재 순서다 기존 컨테이너 벨트는 1번부터 순서대로만 꺼낼 수 있다 보조 벨트는 스택처럼 마지막에 넣은 것부터 꺼낼 수 있다 원하는 순서대로 최대한 실을 수 있는 상자 개수를 구하는 문제다 처음에는 기존 벨트를 실제 리스트로 만들어…
롤케이크 자르기
topping 배열은 롤케이크에 일렬로 올라간 토핑 번호다 한 지점을 잘라 두 조각으로 나눴을 때, 양쪽 토핑 종류 수가 같아야 공평하게 나눈 것이다 공평하게 자를 수 있는 방법의 수를 구하는 문제다 처음에는 자르는 위치마다 왼쪽과 오른쪽 배열을 나눠서 각각 서로 다른 토핑…
할인 행사
want, number 배열로 정현이가 원하는 제품과 수량을 표현한다 discount 배열은 XYZ 마트가 매일 할인하는 제품 목록이다 연속된 10일 동안 할인 제품 종류와 수량이 want, number와 정확히 일치해야 회원가입할 수 있다 그런 시작일이 총 몇 번 있는지…
숫자 변환하기
자연수 x를 y로 바꾸는 데 x+n, x2, x3 세 가지 연산을 쓸 수 있다 x를 y로 바꾸는 최소 연산 횟수를 구하는 문제다 만들 수 없으면 -1을 반환한다 처음에는 x에서 시작해서 세 가지 연산을 재귀적으로 다 시도해보고 y에 도달하는 경로 중 가장 짧은 걸 고르면…