[Algorithm] 기둥과 보 설치

1. 먼저 주어진 표를 행렬로 표현하기 편하도록 아래의 그림과 같이 생각한다.

y = 0 이 바닥이 되고, x = 0이 왼쪽 끝이 된다.

 

2. 없는 것을 삭제하거나 설치된 곳에 설치하지 않는다고 하니 검증하는 단계가 없어도 된다.

삭제와 설치에 대해서 실행하고 가능한지 판단하고 안되면 복구한다.

 

3. 가능한지 점검할 때는 주어진 조건에 따라 조건을 맞춰 검증한다.

public boolean possible(ArrayList<ArrayList<Integer>> answer) {
        for (int i = 0; i < answer.size(); i++) {
            int x = answer.get(i).get(0);
            int y = answer.get(i).get(1);
            int stuff = answer.get(i).get(2);
            if (stuff == 0) { // 설치된 것이 '기둥'인 경우
                boolean check = false;
                // '바닥 위'라면 정상
                if (y == 0) check = true;
                // '보의 한 쪽 끝 부분 위' 혹은 '다른 기둥 위'라면 정상
                for (int j = 0; j < answer.size(); j++) {
                    if (x - 1 == answer.get(j).get(0) && y == answer.get(j).get(1)
                        && 1 == answer.get(j).get(2)) {
                        check = true;
                    }
                    if (x == answer.get(j).get(0) && y == answer.get(j).get(1)
                        && 1 == answer.get(j).get(2)) {
                        check = true;
                    }
                    if (x == answer.get(j).get(0) && y - 1 == answer.get(j).get(1)
                        && 0 == answer.get(j).get(2)) {
                        check = true;
                    }
                }
                if (!check) return false; // 아니라면 거짓(False) 반환
            }
            else if (stuff == 1) { // 설치된 것이 '보'인 경우
                boolean check = false;
                boolean left = false;
                boolean right = false;
                // '한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
                for (int j = 0; j < answer.size(); j++) {
                    if (x == answer.get(j).get(0) && y - 1 == answer.get(j).get(1)
                        && 0 == answer.get(j).get(2)) {
                        check = true;
                    }
                    if (x + 1 == answer.get(j).get(0) && y - 1 == answer.get(j).get(1)
                        && 0 == answer.get(j).get(2)) {
                        check = true;
                    }
                    if (x - 1 == answer.get(j).get(0) && y == answer.get(j).get(1)
                        && 1 == answer.get(j).get(2)) {
                        left = true;
                    }
                    if (x + 1 == answer.get(j).get(0) && y == answer.get(j).get(1)
                        && 1 == answer.get(j).get(2)) {
                        right = true;
                    }
                }
                if (left && right) check = true;
                if (!check) return false; // 아니라면 거짓(False) 반환
            }
        }
        return true;
    }

answer에는 현재 구조물들의 x좌표, y좌표, 구조물 타입이 저장된 리스트들의 집합이다. 

answer 구성

설치된 구조물들을 확인하면서 현재 구조물들이 가능한지 확인한다.

기둥일 때 조건

1) 바닥에 세울 수 있다. y == 0

2) 보의 한쪽 끝부분이거나 다른 기둥 위라면 세울 수 있다.

 (x-1, y) 좌표에 보(1) 이거나(OR) (x, y) 좌표에 보(1) 이거나(OR) (x, y-1) 좌표에 기둥(0)

 

보일 때 조건

1) 한쪽 끝 부분이 기둥 위

 (x, y-1) 좌표에 기둥 (1) 이거나(OR) (x+1, y-1) 좌표에 기둥(1)

2) 양쪽 끝부분이 다른 보와 동시에 연결

 (x-1, y) 좌표에 보(0) 이면서(AND) (x+1, y) 좌표에 보(0)

 

위 조건이 성립하는 경우 true를 출력한다.

 

설치나 삭제 후 조건 확인에 따라 문제가 있다면 다시 설치하거나 다시 삭제하거나.

import java.util.*;

class Node implements Comparable<Node> {
    private int x;
    private int y;
    private int stuff;
    
    public Node (int x, int y, int stuff) {
        this.x = x;
        this.y = y;
        this.stuff = stuff;
    }
    
    public int getX() {
        return this.x;
    }
    
    public int getY() {
        return this.y;
    }
    
    public int getStuff() {
        return this.stuff;
    }
    
    public int compareTo(Node other) {
        if (this.x == other.getX() && this.y == other.getY()) {
            return Integer.compare(this.stuff, other.getStuff());
        } else if (this.x == other.getX()) {
            return Integer.compare(this.y, other.getY());
        } else {
            return Integer.compare(this.x, other.getX());
        }
    }
}

class Solution {
    
    public static ArrayList<ArrayList<Integer>> answer = new ArrayList<>();
    
    public boolean possible(ArrayList<ArrayList<Integer>> answer) {
        for (int i = 0; i < answer.size(); i++) {
            int x = answer.get(i).get(0);
            int y = answer.get(i).get(1);
            int stuff = answer.get(i).get(2);
            if (stuff == 0) { // 설치된 것이 '기둥'인 경우
                boolean check = false;
                // '바닥 위'라면 정상
                if (y == 0) check = true;
                // '보의 한 쪽 끝 부분 위' 혹은 '다른 기둥 위'라면 정상
                for (int j = 0; j < answer.size(); j++) {
                    if (x - 1 == answer.get(j).get(0) && y == answer.get(j).get(1)
                        && 1 == answer.get(j).get(2)) {
                        check = true;
                    }
                    if (x == answer.get(j).get(0) && y == answer.get(j).get(1)
                        && 1 == answer.get(j).get(2)) {
                        check = true;
                    }
                    if (x == answer.get(j).get(0) && y - 1 == answer.get(j).get(1)
                        && 0 == answer.get(j).get(2)) {
                        check = true;
                    }
                }
                if (!check) return false; // 아니라면 거짓(False) 반환
            }
            else if (stuff == 1) { // 설치된 것이 '보'인 경우
                boolean check = false;
                boolean left = false;
                boolean right = false;
                // '한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
                for (int j = 0; j < answer.size(); j++) {
                    if (x == answer.get(j).get(0) && y - 1 == answer.get(j).get(1)
                        && 0 == answer.get(j).get(2)) {
                        check = true;
                    }
                    if (x + 1 == answer.get(j).get(0) && y - 1 == answer.get(j).get(1)
                        && 0 == answer.get(j).get(2)) {
                        check = true;
                    }
                    if (x - 1 == answer.get(j).get(0) && y == answer.get(j).get(1)
                        && 1 == answer.get(j).get(2)) {
                        left = true;
                    }
                    if (x + 1 == answer.get(j).get(0) && y == answer.get(j).get(1)
                        && 1 == answer.get(j).get(2)) {
                        right = true;
                    }
                }
                if (left && right) check = true;
                if (!check) return false; // 아니라면 거짓(False) 반환
            }
        }
        return true;
    }
    
    public int[][] solution(int n, int[][] build_frame) {
        for (int[] frame : build_frame) {
            int x = frame[0];
            int y = frame[1];
            int stuff = frame[2];
            int build = frame[3];
            if (build == 0) {
                // 설치
                int index = 0;
                for(int i = 0; i < answer.size(); i++) {
                    if (x == answer.get(i).get(0) && y == answer.get(i).get(1)
                        && stuff == answer.get(i).get(2)){
                        index = i;
                    }
                }
                ArrayList<Integer> erased = answer.get(index);
                answer.remove(index);
                if (!possible(answer)) {
                    answer.add(erased);
                }
            }
            if (build == 1) { // 설치하는 경우
                // 일단 설치를 해 본 뒤에
                ArrayList<Integer> inserted = new ArrayList<Integer>();
                inserted.add(x);
                inserted.add(y);
                inserted.add(stuff);
                answer.add(inserted);
                if (!possible(answer)) { // 가능한 구조물인지 확인
                    answer.remove(answer.size() - 1); // 가능한 구조물이 아니라면 다시 제거
                }
            }
        }

        // 정렬 수행
        ArrayList<Node> ans = new ArrayList<Node>();
        for (int i = 0; i < answer.size(); i++) {
            ans.add(new Node(answer.get(i).get(0), answer.get(i).get(1), answer.get(i).get(2)));
        }
        Collections.sort(ans);
        
        // 배열로 바꾸어 반환
        int[][] res = new int[ans.size()][3];
        for (int i = 0; i < ans.size(); i++) {
            res[i][0] = ans.get(i).getX();
            res[i][1] = ans.get(i).getY();
            res[i][2] = ans.get(i).getStuff();
        }
        return res;
        
    }
}

마지막에 정렬해서 반환한다.