[Programmers] 기둥과 보 설치 (Level 3)

1. 문제 설명

 

프로그래머스

 

최근 무지성으로 코테 문제를 줄줄이 풀고 있는데, 재밌는 구현 문제가 있어서 소개.

 

특정 조건에 따라 기둥과 보를 추가 혹은 삭제하면 되는데, N이 매우 작아서 재미삼아 풀어보기 좋다.

 

---

2. 아이디어

 

한 번에 풀지 못 했을 때를 대비해서라도 기둥과 보의 설치 조건을 검증하는 비즈니스 규칙을 분리하면 좋다.

 

코드로 보여주자면, 다음과 같이 메서드를 분리하고 시작하는 게 편하다.

// 기둥이라면
if (type == 0) {
    if (action == 0) {
        removePillar(x, y);
    } else {
        buildPillar(x, y);                    
    }
}
            
// 보라면
if (type == 1) {
    if (action == 0) {
        removeBeam(x, y);
    } else {
        buildBeam(x, y);
    }
}

이렇게 하면 테스트에 실패했을 때, 해당하는 부분만 수정을 하면 끝이다.

 

삭제는 조건이 까다로울 것 같으므로, 일단 설치 조건을 먼저 파악해보자.

• 기둥 설치 조건
  • 바닥이라면 무조건 가능
  • 아래에 기둥이 있으면 가능
  • 아래에 보가 있으면 가능
• 보 설치 조건
  • 한쪽 끝 부분이 기둥에 있으면 가능
  • 양쪽 끝 부분이 다른 보와 동시에 연결되면 가능

 

두 비즈니스 검증 규칙을 메서드로 표현하면 다음과 같다.

// 기둥을 설치하는 조건
// - 바닥이어야 함.
// - 아래 기둥이 있어야 함.
// - 아래에 보가 있어야 함.
private boolean isBuildPillar(int x, int y) {
    // 바닥이면 무조건 가능
    if (y == 0) return true;
    // 바로 아래 기둥이 존재하는 경우
    if (pillar[y-1][x] == 1) return true;
    // 왼쪽 아래, 혹은 바로 아래에 보가 존재하는 경우
    if (beam[y][x] == 1 || (x-1 >= 0 && beam[y][x-1] == 1)) return true;
        
    return false;
}
    
// 보를 설치하는 조건
// - 한쪽 끝 부분이 기둥에 있어야 함
// - 양쪽 끝 부분이 다른 보와 동시에 연결되어야 함.
private boolean isBuildBeam(int x, int y) {
    // 아래 혹은 우측 하단에 기둥 존재 여부 확인
    if (y-1 >= 0 && (pillar[y-1][x] == 1 || (x+1 <= N) && pillar[y-1][x+1] == 1)) return true;
    // 양쪽 모두 보가 존재
    if ((x-1 >= 0 && beam[y][x-1] == 1) && (x+1 < N) && beam[y][x+1] == 1) return true;
        
    return false;
}

같은 좌표에 기둥과 보가 둘 다 존재할 수 있으므로, 배열은 두 가지 따로 준비해두어야 한다.

추가는 매우매우 쉬우므로 자세히 설명하는 건 패스하고, 다음은 삭제 조건.

 

기둥이나 보를 삭제할 때, 기존 건축물이 유지될 수 있는 지를 판단해야 한다.

"삭제 조건"을 검증하는 메서드를 만들 수도 있겠지만, "일단 삭제하고, 안 되면 롤백"으로 접근하면 더 편하다.

// 기둥을 제거하는 조건
// - 위에 기둥이 없어야 함.
// - 위의 보가 있다면, 양쪽 끝 부분에 다른 보와 연결되어 있거나, 한쪽 끝이 기둥에 있어야 함. 
private void removePillar(int x, int y) {
    pillar[y][x] = 0;
        
    if (!isRemove(x, y)) { // 삭제해보고 안 되면 rollback
        pillar[y][x] = 1;
    }
}
    
// 보를 제거하는 조건 (바닥에 보를 설치하는 조건은 없음)
// - 한쪽 끝에 기둥이 없어야 함.
// - 기둥이 있다면, 다른 보가 지탱하고 있어야 함.
// - 양쪽을 보에만 의지하고 있는 이웃한 보가 없어야 함.
private void removeBeam(int x, int y) {
    beam[y][x] = 0;
        
    if (!isRemove(x, y)) { // 삭제해보고 안 되면 롤백
        beam[y][x] = 1;
    }
}

 

이게 무슨 소린가 하면, 일단 현재 기둥 혹은 보를 삭제하고

영향을 받는 범위 내의 기둥 혹은 보가 유지될 수 있는 지를 판단하면 된다.

이 때, "유지될 수 있는 지"는 "설치 조건"과 동일하다는 것이 핵심.

 

즉, 이미 위에서 구현한 isBuild()를 재활용하면 되긴 하는데, 영향을 받는 범위 내 모든 영역을 판단해야 하니 isRemove()라는 메서드를 하나 더 경유하도록 만들었다.

 

여기서 isRemove()의 인자로 기둥을 지웠는지, 보를 지웠는지는 전달할 필요가 없다. (type 파라미터를 굳이 추가로 보낼 필요가 없다는 뜻)

만약 기둥을 삭제했을 때와, 보를 삭제했을 때 영향을 전파 받는 영역을 구분하고 싶다면 필요하겠지만,

어차피 N이 100이하 자연수, build_frame 원소 개수는 1000 이하 자연수이므로, 설령 전수조사를 한다고 해도 1000 * 100 * 100 = 10,000,000 밖에 안 된다. 

 

하지만 전수 조사까지 할 필요는 할 필요없고, 어차피 현재 구조물을 제거했을 때 영향을 주는 범위는

(y, x)를 포함한 8방향의 좌표의 건축물들만 확인하면 된다.

 

private static final int[][] dydx = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

private boolean isRemove(int x, int y) {
    for (int direction = 0; direction<9; ++direction) {
        int ny = y - dydx[direction][0], nx = x - dydx[direction][1];
            
        if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
            
        if (pillar[ny][nx] != 0 && !isBuildPillar(nx, ny)) return false;
        if (beam[ny][nx] != 0 && !isBuildBeam(nx, ny)) return false;
    }
        
    return true;
}

여기서 현재 좌표도 반드시 포함해주어야 한다. (이거 빼먹었다가 10분을 더 풀었다 ^^)

 

처음에 카카오 기출이길래 살짝 쫄았는데, 아마 구현 문제 + 난이도를 고려하면 1번 문제가 아니었을까 싶다.

재미삼아 풀어보기 좋은 구현 문제라서 블로그에 기록.

 

---

3. 코드

 

import java.util.*;

class Solution {
    private static final int[][] dydx = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
    private int[][] pillar;
    private int[][] beam;
    private int N;
    
    // 기둥: 바닥 위 or 보의 한쪽 끝 or 다른 기둥 위
    // 보: 한쪽 끝 부분이 기둥 위 or 양쪽 끝 부분이 다른 보와 동시 연결
    // 바닥: 배열(벽면)의 가장 마지막 row
    // 배열은 n * n 크기, 각 격자는 1 * 1 크기
    // build_frame : 작업 순서 (x, y, a:0(기둥)/1(보), b:0(삭제)/1(설치)) -> 설치 불가능하면 패스
    // 결과: 모든 명령어를 수행한 후 구조물 상태 (이차원 배열 (x, y, a) -> x, y, a 순 오름차순 정렬)
    public int[][] solution(int n, int[][] build_frame) {
        N = n;
        pillar = new int[n+1][n+1];
        beam = new int[n+1][n+1];
        
        for (int i=0; i<build_frame.length; ++i) {
            int x = build_frame[i][0], y = build_frame[i][1];
            int type = build_frame[i][2], action = build_frame[i][3];
            
            // 기둥이라면
            if (type == 0) {
                if (action == 0) {
                    removePillar(x, y);
                } else {
                    buildPillar(x, y);                    
                }
            }
            
            // 보라면
            if (type == 1) {
                if (action == 0) {
                    removeBeam(x, y);
                } else {
                    buildBeam(x, y);
                }
            }
        }

        return calcResult();
    }
    
    private void buildPillar(int x, int y) {
        if (!isBuildPillar(x, y)) return;
        
        pillar[y][x] = 1;
        // System.out.println("(" + x + ", " + y + ")에 기둥 추가 (+)");
    }
    
    // 기둥을 제거하는 조건
    // - 위에 기둥이 없어야 함.
    // - 위의 보가 있다면, 양쪽 끝 부분에 다른 보와 연결되어 있거나, 한쪽 끝이 기둥에 있어야 함. 
    private void removePillar(int x, int y) {
        pillar[y][x] = 0;
        
        if (!isRemove(x, y)) { // 삭제해보고 안 되면 rollback
            pillar[y][x] = 1;
        }
        // else System.out.println("(" + x + ", " + y + ")에 기둥 제거 (-)");
    }
    
    private void buildBeam(int x, int y) {
        if (!isBuildBeam(x, y)) return;
        
        // System.out.println("(" + x + ", " + y + ")에 보 추가 (+)");
        
        beam[y][x] = 1;
    }
    
    // 보를 제거하는 조건 (바닥에 보를 설치하는 조건은 없음)
    // - 한쪽 끝에 기둥이 없어야 함.
    // - 기둥이 있다면, 다른 보가 지탱하고 있어야 함.
    // - 양쪽을 보에만 의지하고 있는 이웃한 보가 없어야 함.
    private void removeBeam(int x, int y) {
        beam[y][x] = 0;
        
        if (!isRemove(x, y)) { // 삭제해보고 안 되면 롤백
            beam[y][x] = 1;
        }
        // else System.out.println("(" + x + ", " + y + ")에 보 제거 (-)");
    }
    
    private boolean isRemove(int x, int y) {
        for (int direction = 0; direction<9; ++direction) {
            int ny = y - dydx[direction][0], nx = x - dydx[direction][1];
            
            if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
            
            if (pillar[ny][nx] != 0 && !isBuildPillar(nx, ny)) return false;
            if (beam[ny][nx] != 0 && !isBuildBeam(nx, ny)) return false;
        }
        
        return true;
    }
    
    // 기둥을 설치하는 조건
    // - 바닥이어야 함.
    // - 아래 기둥이 있어야 함.
    // - 아래에 보가 있어야 함.
    private boolean isBuildPillar(int x, int y) {
        // 바닥이면 무조건 가능
        if (y == 0) return true;
        // 바로 아래 기둥이 존재하는 경우
        if (pillar[y-1][x] == 1) return true;
        // 왼쪽 아래, 혹은 바로 아래에 보가 존재하는 경우
        if (beam[y][x] == 1 || (x-1 >= 0 && beam[y][x-1] == 1)) return true;
        
        return false;
    }
    
    // 보를 설치하는 조건
    // - 한쪽 끝 부분이 기둥에 있어야 함
    // - 양쪽 끝 부분이 다른 보와 동시에 연결되어야 함.
    private boolean isBuildBeam(int x, int y) {
        // 아래 혹은 우측 하단에 기둥 존재 여부 확인
        if (y-1 >= 0 && (pillar[y-1][x] == 1 || (x+1 <= N) && pillar[y-1][x+1] == 1)) return true;
        // 양쪽 모두 보가 존재
        if ((x-1 >= 0 && beam[y][x-1] == 1) && (x+1 < N) && beam[y][x+1] == 1) return true;
        
        return false;
    }
    
    private int[][] calcResult() {
        List<int[]> view = new ArrayList<>();
        for (int x=0; x<=N; ++x) for (int y=0; y<=N; ++y) {
            if (pillar[y][x] != 0) {
                int[] elem = {x, y, 0};
                view.add(elem);
            }
            
            if (beam[y][x] != 0) {
                int[] elem = {x, y, 1};
                view.add(elem);
            }
        }
        
        int[][] answer = new int[view.size()][3];
        for (int i=0; i<view.size(); ++i) {
            answer[i] = view.get(i);
        }
        
        return answer;
    }
}