파괴되지 않은 건물

NJW·2023년 5월 6일

kakao

코테

목록 보기

160/170

문제 설명

문제 풀이

첫 번째 접근

처음에 떠오른 생각은 그냥 다 계산해주는 거다. 너비 우선 탐색으로 일일히 구하고 양수인 것만 세주면 그게 답이잖아?

하지만, 여기서 간과하면 안 될 조건이 있으니 바로 해당 문제는 정확성과 효율성 테스트가 각각 있는 문제라는 거다. 효율성 테스트! 때문에 이렇게 풀면 무조건 통과를 못 한다. 이제껏 효율성 테스트에서 눈물을 흘렸던 나의 본능이랄까...

그럼 효율성 테스트를 통과하기 위해서 어떻게 문제를 풀어야 하지?
모르겠다.

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ....

그래서 일단은 정확성 테스트라도 통과해보자 싶은 마음으로 깊이 우선 탐색을 이용해 코드를 짰다.

사실 깊이 우선 탐색을 이용해 효율성 테스트를 무시한 풀이는 굉장히 간단하다.

일단 board의 값을 넣은 mpa을 전역 변수로 설정한다.
모든 skill을 돌면서 너비 우선 탐색을 진행한다. 이때 만일 type이 1이라 공격이라면 degree에다가 -1을 곱해서 더하기를 할 때 빼주도록 한다.
깊이 우선 탐색을 먼저 시작할 때는 해당 위치를 방문했다는 의미로 visit 함수에 true를 넣어준다. 그리고 큐에 값을 넣는다. 다음에 degree를 더해서 현재 위치의 건물 내구도를 정해준다. while을 돌면서 queue가 0이 될 때까지 반복문을 진행하는데, 여기서 새로운 위치의 범위는 시작하는 위치보다 크거나 같고 끝나는 위치보다 작거나 같아야 한다. 만일 새로운 위치를 방문하지 않았다면 새로운 위치의 건물 내구도를 정해주고 새로운 위치를 방문했다고 표시한 뒤 큐에 넣어주면 된다.
모든 스킬들을 돌았다면 마지막으로 끝난 배열을 돌면서 양수인 건물들에만 answer을 더해서 반환해주면 된다.

두 번째 접근

효율성 테스트를 어떻게 풀건지 해답을 구하기 위해 다른 사람의 풀이를 참고했다.

https://jangcenter.tistory.com/121

해당 풀이에서는 누적합을 이용해서 풀었는데, 일단 누적합 기준의 위치를 변경한 후에 맨 마지막에 변화량을 합산하는 방식을 사용했다.

간단하게 말하자면 합을 할 범위의 끝점에 변경 degree를 미리 놓아두고 맨 마지막에 상하좌우로 전부 계산해주는 풀이다.

이건 더 정확한 설명을 위해 위의 링크를 참고하길 바란다. 그림도 있어서 이해가 쉽게 될 것이다.

코드

Only 정확성 테스트 풀이

import java.util.*;

class pair{
    int row;
    int col;
    
    pair(int row, int col){
        this.row = row;
        this.col = col;
    }
}

class Solution {
    public static int[][] map;
    public static int[] dR = {-1, 0, 1, 0}; //북동남서
    public static int[] dC = {0, 1, 0, -1}; //북동남서
    public static boolean[][] visit;
    public static int lengthR, lengthC;
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        map = new int[board.length][board[0].length];
        
        lengthR = map.length;
        lengthC = map[0].length;
        
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                map[i][j] = board[i][j];
            }
        }
        
        
        for(int i=0; i<skill.length; i++){
            int[] cSkill = skill[i];
            
            int type = cSkill[0];
            int startR = cSkill[1];
            int startC = cSkill[2];
            int endR = cSkill[3];
            int endC = cSkill[4];
            int cDegree = cSkill[5];
            
            visit = new boolean[lengthR][lengthC];
            
            //공격을 의미
            if(type == 1){
                cDegree *= -1;
            }
            
            
            bfs(startR, startC, endR, endC, cDegree);
            
            
        }
        
        answer = check();
        
        return answer;
    }
    
        
    public static void bfs(int startR, int startC, int endR, int endC, int degree){
        Queue<pair> queue = new LinkedList<>();
        visit[startR][startC] = true;
        queue.add(new pair(startR, startC));
        map[startR][startC] += degree;
        //System.out.println("current " + startR + " " + startC + " " + degree);
        
        while(!queue.isEmpty()){
            pair current = queue.poll();
            int currentR = current.row;
            int currentC = current.col;
            
            for(int i=0; i<4; i++){
                int newR = currentR + dR[i];
                int newC = currentC + dC[i];
                
                if(newR >= startR && newR <= endR && newC >= startC && newC <= endC){
                    if(visit[newR][newC] == false){
                        map[newR][newC] += degree;
                        //System.out.println("move to " + newR + " " + newC + " " + degree);
                        visit[newR][newC] = true;
                        queue.add(new pair(newR, newC));
                    }
                }
            }
        }
        
        //System.out.println();

    }
    
    public static int check(){
        int answer = 0;
        
        for(int i=0; i<lengthR; i++){
            for(int j=0; j<lengthC; j++){
                if(map[i][j] > 0){
                    //System.out.println(i + " " + j);
                    answer++;
                }
            }
        }
        
        return answer;
    }

}

정확성 + 효율성 풀이

import java.util.*;

class Solution {
    public static int[][] map; 
    public static int lengthR, lengthC;
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        map = new int[board.length+2][board[0].length+2];
        
        lengthR = board.length;
        lengthC = board[0].length;
        

        for(int i=0; i<skill.length; i++){
            int[] current = skill[i];
            
            int type = current[0];
            int startR = current[1];
            int startC = current[2];
            int endR = current[3];
            int endC = current[4];
            int degree = current[5];
            
            if(type == 1){
                degree *= -1;
            }
            
            map[startR][startC] += degree;
            map[startR][endC+1] += degree*-1;
            map[endR+1][startC] += degree*-1;
            map[endR+1][endC+1] += degree;
        }
        
        ope();
            
        for(int i=0; i<lengthR; i++){
            for(int j=0; j<lengthC; j++){
                if(map[i][j] + board[i][j] > 0){
                    answer++;
                }
            }
        }

        return answer;
    }
    
    
    public static void ope(){
        
        //상하
        for(int i=1; i<lengthR; i++){
            for(int j=0; j<lengthC; j++){
                //위에 있는 값과 현재 값을 더해준다.
                map[i][j] += map[i-1][j];
            }
        }
        
        //좌우
        for(int j=1; j<lengthC; j++){
            for(int i=0; i<lengthR; i++){
                //왼쪽에 있는 값과 현재 값을 더해준다.
                map[i][j] += map[i][j-1];
            }
        }
    }

}