[2025 프로그래머스 코드챌린지 1차 예선] 지게차와 크레인(Java)

요구사항

알파벳 대문자로 구분된 컨테이너가 적치 된 물류 창고는

창고 외부와 연결된 컨테이너만 꺼낼 수 있는 지게차와 모든 컨테이너를 꺼낼 수 있는 크레인이 있다.

필요한 컨테이너와 컨테이너를 꺼낼 대 사용 되는 수단을 요청받았을 때 모든 요청을 처리한 후 남은 컨테이너 수 구하기

 

 

입력 값

String[] storage	물류창고 내 컨테이너 정보 문자열 배열 storage[i] 는 i+1 번째 줄의 컨테이너(A-Z) 목록
String[] requests	꺼내야 하는 컨테이너에 대한 요청 정보 문자열(A-Z 또는 AA-ZZ) 배열 requests[i] 는 i+1 번째 요청 A-Z 형태로 한글자인 경우 : 크레인으로 컨테이너 제거 (위치와 상관없이 전체 제거) AA-ZZ 형태로 두글자인 경우 : 지게차로 컨테이너 제거 (바깥쪽에서 접근이 가능한 컨테이너만 제거)

 

 

풀이

1. 지게차(BFS) 탐색에 사용 될 변수 생성

int warehouseX = storage[0].length(); int warehouseY = storage.length;	물류 창고 가로 길이, 세로 길이
int[] dx = {0, 0, -1, 1}; int[] dy = {-1, 1, 0, 0};	BFS 탐색용 x축 y축 배열 순서대로 상 하 좌 우 검색에 사용
Queue<int[]> que = new LinkedList<>();	상하좌우 탐색 용 큐
boolean[][] checked;	탐색 여부 저장 배열
int[] now; int nowX, nowY; int newX, newY;	탐색 loop 내에서 사용 될 변수 탐색중인 컨테이너 탐색중인 컨테이너 좌표 상하좌우 탐색중인 컨테이너 좌표

 

2. 요청이 2글자 이상인 경우 크레인 출고

   -> 전체 컨테이너 에서 요청에 해당하는 컨테이너 문자를 "0"(= 빈 공간 표시) 으로 변경

 

3. 요청이 1글자인 경우 지게차 출고를 위해 테두리 탐색

    -> 바깥에서 접근이 가능해야 하므로 테두리부터 탐색

    -> 이미 탐색한 적 있는 경로인 경우 Pass

    -> 테두리에 요청 컨테이너가 있는 경우 해당 위치 문자를 "1"(= 제거 가능 )으로 변경

    -> 재 탐색 방지를 위해 탐색 여부 저장

    -> 빈 공간(= "0") 인 경우 상하좌우 탐색 시작을 위해 Queue 에 Add

 

4. 지게차로 접근 가능 컨테이너 탐색 (BFS)
    -> 이미 탐색한 적 있는 경로인 경우 Pass
    -> 재 탐색 방지를 위해 탐색 여부 저장

    -> 상하좌우 탐색 중 빈 공간(="0")인 경우 다시 Queue에 Add 하여 상하좌우 탐색 반복

    -> 상하좌우 탐색 중 요청 컨테이너가 있는 경우 해당 위치 문자를 제거 가능(="1")으로 변경

 

5. 지게차 출고

    -> 제거 가능(="1") 으로 변경했던 위치를 모두 빈 공간(="0") 으로 변경

 

6. 모든 요청이 끝날 때까지 2~5 반복

 

7. 물류창고 내에 빈 공간(="0") 을 제외한 컨테이너 갯수 카운팅하여 return

 

728x90

 

Java 코드

import java.util.*;

class Solution {
    public int solution(String[] storage, String[] requests) {
        int answer = 0;
        
        int warehouseX = storage[0].length();
        int warehouseY = storage.length;
        
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        
        Queue<int[]> que = new LinkedList<>();
        boolean[][] checked;
        int[] now;
        int nowX, nowY;
        int newX, newY;
        
        for(String req : requests) {
            // 크레인 출고
            if(req.length() > 1) {
                for(int i=0; i<warehouseY; i++) {  
                    storage[i] = storage[i].replaceAll(req.substring(0, 1), "0");
                }
                
                continue;
            }
            
            // 지게차 출고
            for(int i=0; i<warehouseY; i++) {
                for(int j=0; j<warehouseX; j++) {
                    checked = new boolean[warehouseY][warehouseX];

                    // 가장 바깥 라인이 아니거나 이미 탐색한 경우 Pass
                    if((i != 0 && i != warehouseY - 1
                      && j != 0 && j != warehouseX - 1)
                       || checked[i][j]) continue;

                    checked[i][j] = true;

                    // 테두리에 요청 컨테이너가 있는 경우
                    if(req.equals(storage[i].substring(j, j+1))) {
                        storage[i] = storage[i]
                                        .substring(0, j)
                                        .concat("1")
                                        .concat(storage[i].substring(j+1));
                        continue;
                    }

                    // 빈 공간이 아닌 경우 Pass
                    if(!"0".equals(storage[i].substring(j, j+1))) continue;

                    // 상하좌우 탐색용 큐에 추가
                    que.add(new int[]{i, j});

                    while(!que.isEmpty()) {
                        now     = que.poll();
                        nowY    = now[0];
                        nowX    = now[1];

                        // 상하좌우 탐색
                        for(int k=0; k<4; k++) {
                            newY = nowY+dy[k];
                            newX = nowX+dx[k];

                            // 범위 초과하거나 이미 탐색한 경우 Pass
                            if(newY < 0 || newY >= warehouseY
                              || newX < 0 || newX >= warehouseX
                              || checked[newY][newX]) continue;

                            checked[newY][newX] = true;

                            if("0".equals(storage[newY].substring(newX, newX+1))) {
                                que.add(new int[]{newY, newX});
                            } else if (req.equals(storage[newY].substring(newX, newX+1))) {
                                storage[newY] = storage[newY]
                                                    .substring(0, newX)
                                                    .concat("1")
                                                    .concat(storage[newY].substring(newX+1));
                            }
                        }
                    }
                }
            }

            for(int i=0; i<warehouseY; i++) {
                storage[i] = storage[i].replaceAll("1", "0");
            }
        }
        
        for(String st : storage) {
            answer += st.replaceAll("0", "").length();
        }
        
        return answer;
    }
}

 

 

문제 출처

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