[프로그래머스] 지게차와 크레인(JAVA)

문제

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

---

풀이(45분)

import java.util.*;

class Solution {
    static int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int solution(String[] storage, String[] requests) {
        int n = storage.length;
        int m = storage[0].length();
        char[][] warehouse = new char[n][m];

        // 문자열 배열을 char 2D 배열로 변환
        for (int i = 0; i < n; i++) {
            warehouse[i] = storage[i].toCharArray();
        }

        for (String req : requests) {
            char letter = req.charAt(0);

            // **크레인 사용 시 (모든 문자를 제거)**
            if (req.length() == 2) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if (warehouse[i][j] == letter) {
                            warehouse[i][j] = '.'; // 컨테이너 제거
                        }
                    }
                }
                continue;
            }

            // **지게차 사용 시 (접근 가능한 문자만 제거)**
            boolean[][] outside = new boolean[n][m];
            Queue<int[]> queue = new LinkedList<>();

            // **1. 바깥쪽 '.'(빈 공간) 찾기**
            for (int i = 0; i < n; i++) {
                if (warehouse[i][0] == '.') {
                    queue.add(new int[]{i, 0});
                    outside[i][0] = true;
                }
                if (warehouse[i][m - 1] == '.') {
                    queue.add(new int[]{i, m - 1});
                    outside[i][m - 1] = true;
                }
            }
            for (int j = 0; j < m; j++) {
                if (warehouse[0][j] == '.') {
                    queue.add(new int[]{0, j});
                    outside[0][j] = true;
                }
                if (warehouse[n - 1][j] == '.') {
                    queue.add(new int[]{n - 1, j});
                    outside[n - 1][j] = true;
                }
            }

            // **2. BFS로 외부와 연결된 빈 공간 표시**
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                int y = cur[0], x = cur[1];

                for (int[] dir : direction) {
                    int nextY = y + dir[0];
                    int nextX = x + dir[1];

                    if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= m) {
                        continue;
                    }
                    if (warehouse[nextY][nextX] == '.' && !outside[nextY][nextX]) {
                        outside[nextY][nextX] = true;
                        queue.add(new int[]{nextY, nextX});
                    }
                }
            }

            // **3. 접근 가능한 컨테이너 찾기**
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (warehouse[i][j] != letter) continue;

                    boolean accessible = false;

                    // **테두리에 있으면 바로 제거 가능**
                    if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                        accessible = true;
                    } else {
                        // **4방향 중 하나라도 접근 가능하면 제거**
                        for (int[] dir : direction) {
                            int nextY = i + dir[0];
                            int nextX = j + dir[1];

                            if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= m) {
                                accessible = true;
                                break;
                            }
                            if (warehouse[nextY][nextX] == '.' && outside[nextY][nextX]) {
                                accessible = true;
                                break;
                            }
                        }
                    }

                    // **제거할 컨테이너 표시**
                    if (accessible) {
                        warehouse[i][j] = '.';
                    }
                }
            }
        }

        // **남아 있는 컨테이너 개수 세기**
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (warehouse[i][j] != '.') {
                    answer++;
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution(
                new String[]{"AZWQY", "CAABX", "BBDDA", "ACACA"},
                new String[]{"A", "BB", "A"}
        )); // Expected output: 11

        System.out.println(solution.solution(
                new String[]{"HAH", "HBH", "HHH", "HAH", "HBH"},
                new String[]{"C", "B", "B", "B", "B", "H"}
        )); // Expected output: 4
    }
}

 

복잡한 알고리즘이 있기보다는 구현 문제라고 느꼈다.

 

생각보다 시간이 많이 소요된 부분은 중간의 하나를 빼내었을 때 그것이 언제 밖과 맞닿아 꺼낼 수 있게 해 주는지에 대한 처리였다.

 

먼저 중간의 부분을 꺼낸다면 체크를 해두고, 이것의 외측이 빠져나갔을 때 빈 공간을 추가로 확대해주는 것으로 진행하였다.

 

코드 자체가 복잡하고, 사용되는 변수가 많았다.

-> 이런 경우 수도코드를 먼저 정확하게 작성해두고, 풀이를 진행하자!

-> 변수명을 명확하게 작성하고, 주석으로 남겨두자.