[programmers] 지게차와 크레인

20 Apr 2023 in Algorithm on Algorithm

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

import java.util.*;

class Solution {
    public int solution(String[] storage, String[] requests) {
        int answer = 0;
        int xLen = storage.length;
        int yLen = storage[0].length();
        char[][] box = new char[xLen][yLen];

        for(int x = 0 ; x < xLen ; x++){
            for(int y = 0 ; y < yLen ; y++) box[x][y] = storage[x].charAt(y);
        }

        for(String request : requests){
            if(request.length() > 1){
                crane(request,box,xLen,yLen);
            }else{
                forklift(request,box,xLen,yLen);
            }
        }

        for(int x = 0 ; x < xLen ; x++){
            for(int y = 0 ; y < yLen ; y++){
                if(box[x][y] != '0') answer++;
            }
        }

        return answer;
    }

    private void crane(String request, char[][] box, int xLen, int yLen){
        char c = request.charAt(0);
        for(int x = 0 ; x < xLen ; x++){
            for(int y = 0 ; y < yLen ; y++){
                if(box[x][y] == c) box[x][y] = '0';
            }
        }
    }

    private void forklift(String request, char[][] box, int xLen, int yLen) {
        char c = request.charAt(0);
        boolean[][] visited = new boolean[xLen][yLen];
        boolean[][] toRemove = new boolean[xLen][yLen];
        Queue<int[]> queue = new LinkedList<>();

        for (int x = 0; x < xLen; x++) {
            for (int y = 0; y < yLen; y++) {
                if (box[x][y] == '0' && (x == 0 || y == 0 || x == xLen - 1 || y == yLen - 1)) {
                    queue.offer(new int[]{x, y});
                    visited[x][y] = true;
                } else if (box[x][y] == c && (x == 0 || y == 0 || x == xLen - 1 || y == yLen - 1)) {
                    visited[x][y] = true;
                    toRemove[x][y] = true;
                }
            }
        }

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int cx = curr[0];
            int cy = curr[1];

            for (int d = 0; d < 4; d++) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];

                if (nx >= 0 && ny >= 0 && nx < xLen && ny < yLen && !visited[nx][ny]) {
                    if (box[nx][ny] == '0') {
                        queue.offer(new int[]{nx, ny});
                    } else if (box[nx][ny] == c) {
                        toRemove[nx][ny] = true;
                    }
                    visited[nx][ny] = true;
                }
            }
        }

        for (int x = 0; x < xLen; x++) {
            for (int y = 0; y < yLen; y++) {
                if (toRemove[x][y]) {
                    box[x][y] = '0';
                }
            }
        }
    }
}