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

문제 링크

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

문제

문제 링크 참조

제한사항

문제 링크 참조

알고리즘: 구현, 시뮬레이션

풀이

이 문제는 조금 복잡한 구현 문제다. 문제에서 설명하는 규칙을 지키면서 기둥과 보를 설치하고 설치된 구조물을 출력해주면 된다.

내가 구현한 방식은 이렇다.
일단 명령어를 수행한다. (설치 or 삭제)
그리고 해당 명령어를 실행했을 때 규칙에 부합한 지 확인한다.

1. 규칙에 부합하지 않다면 해당 명령어는 무시되어야 하므로 명령어를 실행하기 전 상태로 롤백한다.

2. 규칙에 부합한다면 해당 명령어는 실행되어야 하므로 롤백하지 않는다.

위 같은 풀이가 가능한 이유는 구조물의 설치 유무를 표시하는 배열의 요소는 최대 20,000개이고, 최대 명령어는 1,000개이기 때문이다. -> (최대 연산 20,000,000)

소스 코드

import java.util.*;
class Node {
    int x, y, a;
    Node(int x, int y, int a) {
        this.x = x;
        this.y = y;
        this.a = a;
    }
}
class Solution {
    static boolean[][][] frame;
    static int N;
    public int[][] solution(int n, int[][] build_frame) {
        N = n;
        frame = new boolean[n+1][n+1][2]; //[y좌표][x좌표][구조물] 0은 기둥, 1은 보
        for(int i=0; i<build_frame.length; i++) {
            int x = build_frame[i][0];
            int y = build_frame[i][1];
            int a = build_frame[i][2];
            if(build_frame[i][3] == 0) frame[y][x][a] = false;
            else frame[y][x][a] = true;
            //rule_check
            if(!check_rule()) frame[y][x][a] = !frame[y][x][a]; //back 해주기
        }
        ArrayList<Node> answer_list = new ArrayList<>();
        for(int i=0; i<=n; i++) {
            for(int j=0; j<=n; j++) {
                for(int k=0; k<2; k++) {
                    if(frame[j][i][k]) answer_list.add(new Node(i, j, k));
                }
            }
        }
        int[][] answer = new int[answer_list.size()][3];
        for(int i=0; i<answer_list.size(); i++) {
            answer[i][0] = answer_list.get(i).x;
            answer[i][1] = answer_list.get(i).y;
            answer[i][2] = answer_list.get(i).a;
        }
        return answer;
    }
    
    static boolean check_rule() {
        for(int i=0; i<frame.length; i++) {
            for(int j=0; j<frame[i].length; j++) {
                if(frame[i][j][0] && !check_pillar(j, i)) return false;
                if(frame[i][j][1] && !check_vo(j, i)) return false;
            }
        }
        return true;
    }
    
    static boolean check_pillar(int x, int y) {
        if((y == 0) || (check_range(x-1, y) && frame[y][x-1][1]) || (frame[y][x][1]) || (check_range(x, y-1) && frame[y-1][x][0])) return true;
        return false;
    }
    
    static boolean check_vo(int x, int y) {
        if((check_range(x, y-1) && frame[y-1][x][0]) || (check_range(x+1, y-1) && frame[y-1][x+1][0])) return true;
        else if((check_range(x-1, y) && frame[y][x-1][1]) && (check_range(x+1, y) && frame[y][x+1][1])) return true;
        return false;
    }
    
    static boolean check_range(int x, int y) {
        if((0 <= x && x <= N) && (0 <= y && y <= N)) return true;
        return false;
    }
}