프로그래머스 LV2 - 지게차와 크레인

좌표들을 문자열별로 모아두고 처리하는 것까진 쉽게 생각이 닿았지만,

하나씩 빼내는 과정에서 새로운 가장자리들을 정의하는 것은 쉽지 않았다.

처음엔 단순히 빼내는 상자 주변에 대해서만 고려했는데, 한번 틀리고나니 아차싶었다.

 

하나의 상자가 빠짐으로써, 상자들에 감싸져있던 빈공간이 댐처럼 터져

모두 밖에서 접근가능한 가장자리가 될 수 있다는것.

 

그래서 상자가 빠지는 동시에 주변의 빈공간을 타고 BFS로 퍼져나가,

새로운 가장자리가 될 여지가 있는 상자들을 찾는다.

그리고 퍼져나가며 !isValid가 되는지 확인하고, ( 인덱스 범위를 벗어남으로 외부에서 접근가능한 것으로 간주한다.)

가장자리를 재정의한다.  

 

BFS 내부로직을 짜는데 생각보다 많은시간이 걸렸다.

offset 반복문 이전, 이후에 각각 어떤처리를 해야하는지 너무 헷갈렸다.

결국 반복문 내부에서 다 처리했기 때문에.. 쓸모없는 반복은 조금 더 생겼을 것이다.

또한  isEdge()등을 활용해서 백트래킹도 가능할 것 같지만.

효율성 검사도 없을 뿐더러 내 수준에 이정도면 충분하다. so 충분

 

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    
    Map<Character, List<int[]>> coordiMap;
    int n,m;
    boolean[][] boundary ;
    boolean[][] removed ;
    int[] offsetX = {-1, 0, 1, 0};
    int[] offsetY = {0, -1, 0, 1};
    
    public int solution(String[] storage, String[] requests) {
        // 초기화
        coordiMap = new HashMap<>();
        n = storage.length;
        m = storage[0].length();
        boundary = new boolean[n][m];
        removed = new boolean[n][m];

        int answer = n * m;

        //map에 알파벳 별로 모으기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char al = storage[i].charAt(j);
                List<int[]> coordiList = coordiMap.computeIfAbsent(al, k -> new ArrayList<>());
                coordiList.add(new int[]{i,j});
                if(isEdge(i,j)) boundary[i][j] = true;
            }
        }

        //요청 순차적으로 실행
        for (String request : requests) {
            char[] chars = request.toCharArray();
            boolean isCrain = chars.length > 1; // "A" or "AA"

            char al = chars[0];
            
            List<int[]> coordiList = coordiMap.getOrDefault(al, Collections.emptyList()); //해당 알파벳 전체.
            List<int[]> targetList;
            if(isCrain){
                targetList = coordiList; 
                coordiMap.remove(al); // 해당 알파벳 삭제
            }else{
                targetList = coordiList.stream().filter(coordi -> {
                    int x = coordi[0];
                    int y = coordi[1];
                    return !removed[x][y] && boundary[x][y]; // 지워지지 않았고, 가장자리에 있는것 특정
                }).collect(Collectors.toList());
                coordiList.removeAll(targetList);
                coordiMap.put(al, coordiList); // targetList뺀 나머지로 갱신
            }

            targetList.forEach(coordi -> outBfs(coordi)); //bfs 실행.

            answer -= targetList.size();

        }

        

        return answer;
    }
    
    
    private boolean isEdge(int x, int y) {
        return (x == 0 || x == n-1 || y == 0 || y == m-1);
    }

    private boolean isValid(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < m);
    }

    private void outBfs(int[] coordi){
        int x = coordi[0];
        int y = coordi[1];

        //일단 removed에서 삭제처리.
        removed[x][y] = true;

        Queue<int[]> bfsQueue = new LinkedList<>(); // bfs 큐
        List<int[]> targetNodes = new ArrayList<>(); // 새로운 가장자리가 될 노드들.
        boolean[][] visited = new boolean[n][m]; // 방문 기록
        boolean isOpened = false; //외부와 연결 여부.

        bfsQueue.add(coordi);
        
        while (!bfsQueue.isEmpty()) {
            int[] cur = bfsQueue.poll();
            int cx = cur[0];
            int cy = cur[1];

            for (int o = 0; o < 4; o++) {
                int nx = cx + offsetX[o];
                int ny = cy + offsetY[o];

                if(!isValid(nx, ny)){
                    isOpened = true;
                    continue;
                }
                if(visited[nx][ny]) continue;
                
                if(!removed[nx][ny]){
                    if(!boundary[nx][ny]){
                        targetNodes.add(new int[]{nx,ny}); // 삭제X, 가장자리x 새로운 가장자리 예정.
                    }
                }else{
                    bfsQueue.add(new int[]{nx,ny}); // 삭제O 데이터들만 queue로 추가.
                }

                visited[nx][ny] = true;

            }

        }

        if(isOpened) { // 삭제된 데이터를 타고간 결과 !isValid에 도달한 경우.
            for (int[] node : targetNodes) {
                boundary[node[0]][node[1]] = true; // 새로운 가장자리로 결정
            }
        }
        
    }

}