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

문제 파악

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

풀이

일단 동시에 여러 지점에서 같은 깊이로 탐색이 필요해 BFS로 접근해야겠다는 생각이 들었다
접근은 어렵지 않았지만, 추가 조건들이 존재해 구현이 조금 까다로웠던 문제였다.

조심해야 할 케이스는 다음과 같다

위와 같이 새로 노출되는 영역이 빈 칸일 경우, 빈 칸과 인접한 칸들도 노출된다.
이 케이스를 커버하기 위해 조금만 더 신경쓰면 된다.

구현 방향을 간략히 설명하자면 다음과 같다.

1. 컨테이너 맵의 크기와 동일한 isExposed(boolean[][]) 배열을 선언 및 초기화
   • isExposed 테두리 부분을 true로 초기화하자.
2. isExposed 배열을 참고하여 request에 따라 꺼낼 수 있는 컨테이너들을 꺼내며 업데이트 해 준다.
   
   • 만약 노출된 위치의 컨테이너를 꺼낸 경우, 해당 컨테이너를 별도 큐에 저장해 3의 과정에서 처리한다.
3. 큐에 저장된 컨테이너를 순환하며 노출을 전파한다.
   • 동/서/남/북 위치에 노출을 전파한다.
   • 인접한 위치가 범위를 벗어나거나, 이미 노출된 부분이라면 처리하지 않는다
   • 만약 인접한 위치가 빈 칸이라면, 빈 칸의 인접한 위치도 노출이 필요하므로 큐에 밀어넣어 준다.

 

코드

import java.util.*;

public class Solution {
    private static final int[][] movements = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static Queue<int[]> exposureQueue;
    private static boolean[][] isExposed;
    private static char[][] map;

    public static int solution(String[] storage, String[] requests) {
        init(storage);
        for (String request : requests) {
            char target = request.charAt(0);
            if (request.length() == 2) {
                removeAll(target);
            } else {
                removeExposed(target);
            }
        }
        int answer = 0;
        for (char[] m : map) {
            for (char c : m) {
                answer += c == 0 ? 0 : 1;
            }
        }
        return answer;
    }

    private static void init(String[] storage) {
        int row = storage.length;
        int col = storage[0].length();
        map = new char[row][col];
        isExposed = new boolean[row][col];
        exposureQueue = new LinkedList<>();

        Arrays.fill(isExposed[0], true);
        Arrays.fill(isExposed[row - 1], true);

        for (int i = 0; i < isExposed.length; i++) {
            isExposed[i][0] = isExposed[i][col-1] = true;
        }

        for (int i = 0; i < row; i++) {
            map[i] = storage[i].toCharArray();
        }
    }

    private static void removeAll(char c) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (map[i][j] == c) {
                    map[i][j] = 0;
                    if (isExposed[i][j]) {
                        exposureQueue.offer(new int[]{i, j});
                    }
                }
            }
        }
        spanExposure();
    }

    private static void removeExposed(char c) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (map[i][j] == c && isExposed[i][j]) {
                    map[i][j] = 0;
                    exposureQueue.offer(new int[]{i, j});
                }
            }
        }
        spanExposure();
    }

    private static void spanExposure() {
        while (!exposureQueue.isEmpty()) {
            int[] current = exposureQueue.poll();
            int r = current[0];
            int c = current[1];
            for (int[] m : movements) {
                int nR = r + m[0];
                int nC = c + m[1];
                if (nR < 0 || nR >= map.length || nC < 0 || nC >= map[0].length || isExposed[nR][nC]) {
                    continue;
                }
                isExposed[nR][nC] = true;
                if (map[nR][nC] == 0) { // 추가로 노출된 부분이 빈칸 일 때 노출이 전파되어야 한다
                    exposureQueue.offer(new int[]{nR, nC});
                }
            }
        }
    }
}