[프로그래머스] 기둥과 보 설치

 

 

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

프로그래머스

문제 요약

• 기둥과 보를 2차원 공간에 설치하거나 제거한다.
• 설치 및 삭제는 각각의 조건을 만족해야 한다.
• 최종적으로 남은 구조물들을 (x, y, 구조물 타입) 형식으로 정렬해 반환해야 한다.

---

구조물 상태 표현 방식: 비트마스킹

각 좌표에서 구조물의 상태 관리하기 위해 int[][] map 배열을 사용했다.
각 구조물의 위치 상태는 비트마스크를 활용하여 다음과 같이 정의한다.

static final int PILLAR_START = 1; // 기둥 아래
static final int PILLAR_END   = 2; // 기둥 위
static final int BEAM_START   = 4; // 보 왼쪽
static final int BEAM_END     = 8; // 보 오른쪽

예를 들어, map[x][y]의 값이 PILLAR_START + BEAM_START이면 (x, y) 위치에 기둥과 보가 동시에 설치되어 있음을 의미한다.

---

설치 조건 함수

구조물마다 설치 조건이 다르므로 이를 각각 별도의 함수로 분리하여 정의한다.

private boolean checkPillar(int x, int y) {
    if (y == 0) return true;
    return (map[x][y] & (BEAM_START + BEAM_END + PILLAR_END)) != 0;
}

private boolean checkBeam(int x, int y) {
    if ((map[x][y] & PILLAR_END) != 0 || (map[x + 1][y] & PILLAR_END) != 0) return true;
    return (map[x][y] & BEAM_END) != 0 && (map[x + 1][y] & BEAM_START) != 0;
}

---

삭제 조건 검증 및 롤백 처리

삭제 시 중요한 점은, 삭제로 인해 연결된 구조물이 설치 조건을 위반하는지 확인해야 한다는 점이다.
이를 위해 연결된 구조물만 선별적으로 확인하고, 조건을 위반할 경우 삭제를 롤백한다.

boolean rollback = false;

// 기둥 삭제
map[x][y + 1] -= PILLAR_END;

if ((map[x][y + 1] & BEAM_END) != 0 && !checkBeam(x - 1, y + 1)) rollback = true;
else if ((map[x][y + 1] & BEAM_START) != 0 && !checkBeam(x, y + 1)) rollback = true;
else if ((map[x][y + 1] & PILLAR_START) != 0 && !checkPillar(x, y + 1)) rollback = true;

if (rollback) {
    map[x][y + 1] += PILLAR_END;
} else {
    map[x][y] -= PILLAR_START;
}

보 삭제 또한 동일한 원리로 처리된다.

---

최종 결과 반환

설치가 끝난 후, 모든 좌표를 순회하며 남아 있는 구조물을 정리한다.
문제 조건에 따라 (x → y → 구조물 타입) 순으로 자동 정렬이 되도록 이중 for문을 활용했다.

ArrayList<int[]> result = new ArrayList<>();

for (int x = 0; x <= N; x++) {
    for (int y = 0; y <= N; y++) {
        if ((map[x][y] & PILLAR_START) > 0) result.add(new int[]{x, y, 0});
        if ((map[x][y] & BEAM_START) != 0) result.add(new int[]{x, y, 1});
    }
}

return result.toArray(new int[result.size()][]);

 

---

전체 코드

import java.util.*;

class Solution {
    static final int PILLAR_START = 1;
    static final int PILLAR_END = 2;
    static final int BEAM_START = 4;
    static final int BEAM_END = 8;
    
    static int[][] map;
    static int N;
    
    public int[][] solution(int n, int[][] build_frame) {
        this.N = n;
        
        map = new int[N+2][N+2];
        
        for(int[] frame : build_frame) {
            int x = frame[0];
            int y = frame[1];
            int a = frame[2];
            int b = frame[3];
        
            //설치
            if(b == 1) {
                if(a == 0 && checkPillar(x, y)) {
                    map[x][y] |= PILLAR_START;
                    map[x][y+1] |= PILLAR_END;
                }
                else if(a == 1 && checkBeam(x, y)) {
                    map[x][y] |= BEAM_START;
                    map[x+1][y] |= BEAM_END;
                }
                
                continue;
            }
            
            //삭제
            boolean rollback = false;
            
            //기둥 삭제
            if(a == 0) {
                
                map[x][y+1] -= PILLAR_END; 
                
                if((map[x][y+1] & BEAM_END) != 0 && !checkBeam(x-1, y+1)) {
                    rollback = true;
                }
                else if((map[x][y+1] & BEAM_START) != 0 && !checkBeam(x, y+1)) {
                    rollback = true;
                }
                else if((map[x][y+1] & PILLAR_START) != 0 && !checkPillar(x, y+1)) {
                    rollback = true;
                }
                
                if(rollback)
                    map[x][y+1] += PILLAR_END;
                else
                    map[x][y] -= PILLAR_START;
                
                continue;
            }
            
            //보 삭제
            map[x][y] -= BEAM_START;
            map[x+1][y] -= BEAM_END;
            
            if((map[x][y] & BEAM_END) != 0 && !checkBeam(x-1, y)) {
                rollback = true;
            }
            else if((map[x][y] & PILLAR_START) != 0 && !checkPillar(x, y)) {
                rollback = true;
            }
            else if((map[x+1][y] & BEAM_START) != 0 && !checkBeam(x+1, y)) {
                rollback = true;
            }
            else if((map[x+1][y] & PILLAR_START) != 0 && !checkPillar(x+1, y)) {
                rollback = true;
            }
            
            if(rollback) {
                map[x][y] += BEAM_START;
                map[x+1][y] += BEAM_END;
            }
            
        }
        
        ArrayList<int[]> result = new ArrayList<>();
        
        for(int x=0; x<=N; x++) {
            for(int y=0; y<=N; y++) {
                if((map[x][y] & PILLAR_START) > 0)
                    result.add(new int[] {x, y, 0});
                
                if((map[x][y] & BEAM_START) != 0)
                    result.add(new int[] {x, y, 1});
            }
        }
        System.out.println(result.size());
        return result.toArray(new int[result.size()][]);
    }
    
    private boolean checkPillar(int x, int y) {
        //1. 바닥 위에 있거나.
        if(y==0) {
            return true;
        }
        //2. 보의 한쪽 끝 부분 위에 있거나.
        //3. 다른 기둥 위에 있거나.
        else if((map[x][y] & (BEAM_START + BEAM_END + PILLAR_END )) != 0) {
            return true;
        }
        
        return false;
    }
    
    private boolean checkBeam(int x, int y) {
        //1. 한쪽 끝 부분이 기둥 위에 있거나.
        if((map[x][y] & PILLAR_END) != 0 || (map[x+1][y] & PILLAR_END) != 0) {
            return true;
        }
        //2. 양쪽 끝 부분이 다른 보와 동시에 연결되어 있거나.
        else if((map[x][y] & BEAM_END) != 0  && (map[x+1][y] & BEAM_START) != 0) {
            return true;
        }
        
        return false;
    }
}