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

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

프로그래머스

코딩테스트 연습 > 2025 프로그래머스 코드챌린지 1차 예선 > 지게차와 크레인

 

난이도: LEVEL2

알고리즘 유형: 시뮬레이션

문제 정리

request[i] 길이가 1이면 지게차 길이가 2이면 크레인을 사용

 

지게차: 컨테이너 4면 중 적어도 1면이 외부와 연결된 컨테이너를 제거 

크레인: 요청된 종류의 모든 컨테이너를 제거 

 

request[i] 길이로 지게차, 크레인이 구분되지만 알파벳 종류는 하나, 무조건 대문자이다

문제 접근

먼저 크레인 로직은 정말 간단하다.

request[i] 길이가 2이면 크레인으로 동작인데

해당하는 알파벳을 전부 없애주면 끝이다.

// 크레인 로직 
if(request.length() == 2){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(map[i][j] == target){
                map[i][j] = -1;
            }
        }
    }
    continue;
}

 

문제는 지게차 로직이다. 

 

처음 지게차가 컨테이너가 제거 가능한 위치는 창고 바깥 면 전체이다.

하지만 첫 번째 요청은 'A'제거여서 4개가 제거된다. 

두 번째 요청은 'BB' 크레인 요청 

세 번째 요청은 'A'인데 제거 대상이 하나이다.

 

그럼 제거 대상 구별 방법을 어떻게 구현할까?

 

제거 대상은 바로 제거하지 않는다. → 요청 처리 로직의 제일 마지막에 제거한다. 

창고의 모든 위치를 창고 크기 보다 큰 숫자로 채운다. (재방문 방지)

BFS를 통해서 제거 대상인 컨테이너를 찾는다. → 항상 시작을 바깥 면에서 시작한다. 

이미 제거된 컨테이너의 0으로 기록 (방문 표시) BFS 큐에 넣어준다.

만약 제거되지 않은 컨테이너를 만나면 1로 기록 (방문 표시)
이때 이번 요청의 알파벳과 동일하면 제거 대상 기록 리스트에 넣어준다. 

 

바깥 면만 시작하는 모든 로직(2중 for문)이 끝나면 제거 대상을 기록한 리스트에 있는 위치들을 제거한다. 

 

만약 이렇게 제거 대상을 바로바로 제거하면 어떤 문제점이 발생할까?

다른 시작점(바깥 면)에서 이번에 제거된 컨테이너인지 구분할 방법이 없으니 이번 요청에 외부와 연결되지 않은 컨테이너도 제거될 가능성이 생긴다.

정답 코드 

import java.util.*;
class Solution {
    static final int INF = 10001;
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static int n, m;
    public int solution(String[] storage, String[] requests) {
        int answer = 0;
        n = storage.length;       // 행
        m = storage[0].length();  // 열
        int [][] map = new int [n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                map[i][j] = storage[i].charAt(j) - 'A';
            }
        }
        // 요청 처리 
        for(String request : requests){
            int target = request.charAt(0) - 'A';
            // 크레인 로직 
            if(request.length() == 2){
                for(int i = 0; i < n; i++){
                    for(int j = 0; j < m; j++){
                        if(map[i][j] == target){
                            map[i][j] = -1;
                        }
                    }
                }
                continue;
            }
            // 지게차 로직
            int [][] memo = new int [n][m];
            for(int i = 0; i < n; i++){
                Arrays.fill(memo[i], INF);
            }
            ArrayList<int[]> list = new ArrayList<>();
            Queue<int[]> q = new LinkedList<>();
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(i != 0 && j != 0 && i != n - 1 && j != m - 1) continue;
                    if(memo[i][j] != INF) continue;
                    if(map[i][j] != -1){
                        memo[i][j] = 1;
                        if(map[i][j] == target){
                            list.add(new int []{i,j});
                        }
                        continue;
                    }
                    memo[i][j] = 0;
                    q.add(new int [] {i, j});
                    while(!q.isEmpty()){
                        int [] cur = q.poll();
                        for(int k = 0; k < 4; k++){
                            int nx = cur[0] + arx[k];
                            int ny = cur[1] + ary[k];
                            if(!validation(nx, ny) || memo[nx][ny] != INF) continue;
                            if(map[nx][ny] == -1){
                                memo[nx][ny] = 0;
                                q.add(new int [] {nx, ny});
                                continue;
                            }
                            memo[nx][ny] = 1;
                            if(map[nx][ny] == target){
                                list.add(new int []{nx,ny});
                            }
                        }
                    }
                }
            }   
            // 이번 요청에서 제거 대상인 컨테이너 제거 
            for(int [] next : list){
                map[next[0]][next[1]] = -1;
            }
        }
        
        // 남은 컨테이너 개수 count
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(map[i][j] != -1) answer++;
            }
        }
        return answer;
    }
    
    // Arrays out of index 방지 
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < m) return true;
        return false;
    }
}