[Programmers] 지게차와 크레인 - Java

문제

프로그래머스

 

풀이

물류 창고에 있는 컨테이너를 2가지 방식으로 꺼냈을 때, 남은 컨테이너의 개수를 구하는 문제이다.

 

1. 삭제 처리하는 boolean 2차원 배열을 생성한다.

 

2. 길이 여부에 따라서 크레인이나 지게차로 컨테이너를 꺼냈을 때 처리 한다.

 

2-1. 지게차로 컨테이너를 꺼냈을 때, bfs를 이용한다.

외부에서 꺼낼 컨테이너가 있다면(ch와 같으면서 삭제가 안되었을 경우), 삭제처리와 방문처리를 해준다.(방문처리를 안해주면, 안에 있는 컨테이너도 꺼내질 수 있는 경우가 있을 수 있어서다.)

 

삭제 처리가 된 컨테이너들은 큐에 담아서 bfs를 수행하면서 외부의 정점들을 모두 outList에 담는다.

 

외부 정점에 대해, 상하좌우 방향으로 꺼낼 컨테이너가 있다면, 꺼내준다.

 

2-2. 크레인으로 컨테이너를 꺼내는 것은 외부에서 꺼내는 것과 관계 없으므로, 2중 for문을 통해서 컨테이너를 꺼낸다.

 

3. 꺼내지 않은 컨테이너 개수를 센다.

 

소스코드

import java.util.ArrayList;
import java.util.ArrayDeque;

class Solution {
    public int solution(String[] storage, String[] requests) {
        int n = storage.length;
        int m = storage[0].length();
        
        boolean[][] deleted = new boolean[n][m];
        
        for (String request : requests) {
            char ch = request.charAt(0);
            
            if (request.length() == 1) {
                requestCar(storage, deleted, n, m, ch);
            } else {
                requestCrane(storage, deleted, n, m, ch);
            }
        }
        
        int answer = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!deleted[i][j]) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
    
    static void requestCar(String[] storage, boolean[][] deleted, int n, int m, char ch) {
        ArrayList<int[]> outList = new ArrayList<>();
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        
        boolean[][] visited = new boolean[n][m];
            
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        
        for (int i = 0; i < n; i++) {
            if (!deleted[i][0]) {
                if (storage[i].charAt(0) == ch) {
                    deleted[i][0] = true;
                    visited[i][0] = true;
                }                       
            } else {
                queue.addLast(new int[] {i, 0});
                visited[i][0] = true;
            }
            
            if (!deleted[i][m - 1]) {
                if (storage[i].charAt(m - 1) == ch) {
                    deleted[i][m - 1] = true;
                    visited[i][m - 1] = true;
                }                       
            } else {
                queue.addLast(new int[] {i, m - 1});
                visited[i][m - 1] = true;
            }
        }
        
        for (int i = 0; i < m; i++) {
            if (!deleted[0][i]) {
                if (storage[0].charAt(i) == ch) {
                    deleted[0][i] = true;
                    visited[0][i] = true;
                }                       
            } else {
                queue.addLast(new int[] {0, i});
                visited[0][i] = true;
            }
            
            if (!deleted[n - 1][i]) {
                if (storage[n - 1].charAt(i) == ch) {
                    deleted[n - 1][i] = true;
                    visited[n - 1][i] = true;
                }                       
            } else {
                queue.addLast(new int[] {n - 1, i});
                visited[n - 1][i] = true;
            }
        }
        
        while (!queue.isEmpty()) {
            int[] pos = queue.removeFirst();
            
            outList.add(pos);
            
            for (int i = 0; i < 4; i++) {
                int mx = pos[0] + dx[i];
                int my = pos[1] + dy[i];
                
                if (mx < 0 || mx >= n || my < 0 || my >= m) continue;
                
                if (deleted[mx][my] && !visited[mx][my]) {
                    queue.addLast(new int[] {mx, my});
                    visited[mx][my] = true;
                }
            }
        }
        
        for (int[] pos : outList) {
            for (int i = 0; i < 4; i++) {
                int mx = pos[0] + dx[i];
                int my = pos[1] + dy[i];
                
                if (mx < 0 || mx >= n || my < 0 || my >= m) continue;
                
                if (!deleted[mx][my] && storage[mx].charAt(my) == ch) {
                    deleted[mx][my] = true;
                }
            }
        }
    }
    
    static void requestCrane(String[] storage, boolean[][] deleted, int n, int m, char ch) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!deleted[i][j] && storage[i].charAt(j) == ch) {
                    deleted[i][j] = true;
                }
            }
        }
    }
}

 

실행결과