[프로그래머스] 지게차와 크레인 자바 BFS

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

프로그래머스

문제

storage는 컨테이너의 상황도이며 맨 윗줄부터 순서대로 나열되어 있다.

requets는 꺼낼 요청들의 모음이다.

request가 한글자인 경우 지게차를 사용해서 외곽에서부터 접근하여 꺼내고

두 번 반복되는 경우 크레인으로 한 번에 접근해서 꺼낸다.

 

request를 모두 수행하고 남은 컨테이너의 수를 반환하시오.

 

접근

1.String[][] containers에 storage 정보를 담는다.
2. request를 순회하며 , request의 길이에 따라 처리로직 분리
    지게차 로직일 때, 현 대상 위치가 접근 가능한 위치인지 판단하여 가능하면 꺼낸다.
    크레인 요청의 경우, 대상과 같은 모든 컨테이너를 꺼낸다.

public int solution2(String[] storage, String[] requests) {
        // 컨테이너 배열 초기화
        String[][] containers = new String[storage.length][];
        for (int i =  0; i < storage.length; i++) {
            containers[i] = storage[i].split("");
        }
        int total = containers.length * containers[0].length;
        int removedCount = 0;

        for (String request : requests) {
            String r = request.substring(0, 1);
            //지게차
            if (request.length() == 1) {
                for(int i = 0; i < containers.length; i ++){
                    for(int j = 0; j < containers[i].length; j ++){
                        if(isRemovable(containers, i, j) && r.equals(containers[i][j])){
                            containers[i][j] = null;
                            removedCount++;
                        }
                    }
                }

            } 
            //크레인
            else if (request.length() == 2) {
                for (int i = 0; i < containers.length; i++) {
                    for (int j = 0; j < containers[i].length; j++) {
                        if (r.equals(containers[i][j])) {
                            containers[i][j] = null;
                            removedCount++;
                        }
                    }
                }
            }
        }

        return total - removedCount;
    }
    public boolean isRemovable(String[][] containers, int row, int col) {
        int top = Math.max(row - 1, 0);
        int left = Math.max(col -1, 0);
        int right = Math.min(col + 1, containers[0].length -1);
        int bottom = Math.min(row + 1, containers.length -1);

        boolean isBorder = top == row || bottom == row || col == left || col == right;
        boolean isRemovable = containers[top][col] == null || containers[bottom][col] == null ||containers[row][left] == null || containers[row][right] == null;;

        return isRemovable || isBorder;
    }

발견된 문제

지게차 로직에서, 외곽에서부터 접근가능한지 판단하는 로직이 잘못되었음.
대상이 외곽에 존재하거나 인접 블럭이 null이면 true를 반환하고 있는데, 이것으로는 외곽에서 접근 가능한지 정확하게 알 수 없음.

수정

BFS(Breadth First Search) 너비우선방식
개념 참고링크
https://blog.naver.com/book541/222753851346

 BFS방식을 활용하여 외곽에서부터 접근 가능한지 파악하는 로직을 활용할 수 있다고 하여 적용하였다.

queue 와  int배열 값을 활용해 비교하여 판단하는 로직으로 보이나.. 자세한 동작 과정에 대한 이해는
별도로 디버깅 과정을 통해 학습이 필요하다.

public int solution3(String[] storage, String[] requests) {
		//기존 외곽에 null로 감싸 표현하기 위해 buffer 2 추가.
        int rows = storage.length +2;
        int cols = storage[0].length() +2;
        String[][] containers = new String[rows][cols];
        for (int i = 0; i < storage.length; i++) {
            for( int j = 0; j < storage[i].length(); j++){
                containers[i + 1][j + 1] = String.valueOf(storage[i].charAt(j));
            }

        }

        int total = storage.length * storage[0].length();
        int removedCount = 0;

        for (String request : requests) {
            String target = request.substring(0, 1);

            if (request.length() == 1) {
                // 지게차 : 외곽 컨테이너만 제거 
                boolean[][] outskirts = markOutskirts(containers);
                for (int i = 0; i < rows; i++) {
                    for (int j = 0; j < cols; j++) {
                        if (outskirts[i][j] && target.equals(containers[i][j])) {
                            containers[i][j] = null;
                            removedCount++;
                        }
                    }
                }
            } else {
                // 크레인 : 모두 제거
                for (int i = 0; i < rows; i++) {
                    for (int j = 0; j < cols; j++) {
                        if (target.equals(containers[i][j])) {
                            containers[i][j] = null;
                            removedCount++;
                        }
                    }
                }
            }
        }

        return total - removedCount;
    }
	
    //외곽 판별. DFS로직 적용
    public boolean[][] markOutskirts(String[][] containers) {
        int rows = containers.length;
        int cols = containers[0].length;
        boolean[][] visited = new boolean[rows][cols];
        boolean[][] isOutskirts = new boolean[rows][cols];

        Queue<int[]> queue = new LinkedList<>();

        // 경계에서 null인 칸부터 시작
        for (int i = 0; i < rows; i++) {
            if (containers[i][0] == null) queue.offer(new int[]{i, 0});
            if (containers[i][cols - 1] == null) queue.offer(new int[]{i, cols - 1});
        }
        for (int j = 0; j < cols; j++) {
            if (containers[0][j] == null) queue.offer(new int[]{0, j});
            if (containers[rows - 1][j] == null) queue.offer(new int[]{rows - 1, j});
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        // BFS로 null 공간을 따라 외부 연결 탐색
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];

            if (visited[r][c]) continue;
            visited[r][c] = true;

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;

                if (containers[nr][nc] == null && !visited[nr][nc]) {
                    queue.offer(new int[]{nr, nc});
                }

                // 인접한 컨테이너는 외곽
                if (containers[nr][nc] != null) {
                    isOutskirts[nr][nc] = true;
                }
            }
        }

        return isOutskirts;
    }