388353. 지게차와 크레인

문제

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

제한사항

풀이

1. 창고 맵을 초기화한다. 외부를 구분하기 위해 기존 창고 겉에 외부 빈공간을 구분할 수 있는 배열을 추가한다.

1.1 외부 빈공간은 '0', 내부 빈공간은 '1'로 설정했다.

2. 크레인, 지게차 로직 구현한다. 

2.1 크레인, 지게차가 컨테이너를 제거하면 외부 빈 공간('0')이 생길 수 있다. 그 빈 공간이 내부 빈 공간에 영향을 주는지 확인한다. 외부 빈 공간이 생기면서 주변 내부 빈 공간('1')이 외부 빈 공간('0')이 될 수 있다.

import java.util.*;

class Solution {
    public int solution(String[] storage, String[] requests) {
        
        int n = storage.length;
        int m = storage[0].length();
        int boxCnt = 0;
        char [][] storageArray = new char[n+2][m+2];
        
        // 창고 배열 초기화
        for(int i = 0 ; i< n+2; i++)
            for(int j =0; j<m+2; j++) {
                if(i==0 || j ==0 || i == n+1 || j == m+1)
                    storageArray[i][j] = '0';
                
                else {
                 storageArray[i][j] = storage[i-1].charAt(j-1);   
                }
            }
            
        for(String r : requests) {
            if(r.length() == 1)
                fork(storageArray, r.charAt(0));
            else
                crane(storageArray, r.charAt(0));
        }

        for(int i=1;i<n+1;i++)
            for(int j =1 ;j< m+1;j++) {
                if(storageArray[i][j]!='0' && storageArray[i][j]!='1') {
                    System.out.println("box: " + storageArray[i][j]);
                    boxCnt++;
                }
                    
            }
        
        int answer = boxCnt;
        return answer;
    }
    
    void fork(char[][] storageArray, char box) {
        int n = storageArray.length;
        int m = storageArray[0].length;
        Queue<int[]> boxesToRemoveQueue = new LinkedList<>();
        
        for(int i = 1; i< n-1; i++)
            for(int j =1; j < m-1; j++) {
                if(storageArray[i][j] == box && isOutside(storageArray, i, j)) {
                    // storageArray[i][j] = '0';
                    boxesToRemoveQueue.offer(new int[]{i,j});
                }
            }
        
        while(!boxesToRemoveQueue.isEmpty()) {
            int[] p = boxesToRemoveQueue.poll();
            storageArray[p[0]][p[1]] = '0';
            expandOutside(storageArray, p[0], p[1]);
        }
        
    }
    
    void crane(char[][] storageArray, char box) {
        int n = storageArray.length;
        int m = storageArray[0].length;
        
        for(int i = 1 ; i < n-1; i++)
            for(int j =1; j < m-1; j++) {
                if(storageArray[i][j] == box) {
                    // storageArray[i][j] = '1';
                    
                    if(isOutside(storageArray, i, j)) {
                        storageArray[i][j] = '0';   
                        expandOutside(storageArray, i, j);
                    }
                    else
                        storageArray[i][j] = '1';
                }
            }
    }
    
    boolean isOutside(char[][] storageArray, int row, int col) {
        int[][] dir = {{0,1}, {0, -1}, {1, 0}, {-1, 0}};
        
        for(int i = 0; i< 4; i++) {
            
            if(storageArray[row+dir[i][0]][col+dir[i][1]] == '0')
                return true;
            
        }
        
        return false;
    }
    
    void expandOutside(char[][] storageArray, int row, int col) {
        int[][] dir = {{0,1}, {0, -1}, {1, 0}, {-1, 0}};
        Queue<int[]> queue = new LinkedList<>();
        int n = storageArray.length;
        int m = storageArray[0].length;
        queue.offer(new int[]{row, col});
        
        while(!queue.isEmpty()) {
            int [] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            for(int i =0; i < 4;i++) {
                int nr = r + dir[i][0];
                int nc = c + dir[i][1];
            if(nr>0 && nr<n && nc>0 && nc<m && storageArray[nr][nc] == '1') {
                storageArray[nr][nc] = '0';
                queue.offer(new int[]{nr, nc});
            }
        }
          
        }
        
    }
}

회고

일부 테스트 코드를 실패해서 풀이를 봤다. 컨테이너 제거하는 과정에서, 마지막엔 항상 컨테아너 제거로 주변 컨테이너가 외부 공간('0')이 되는지 확인을 해줘야 하는 걸 놓쳤다.