Lv 2. 지게차와 크레인

 

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

프로그래머스

 

 

 

📌 자바(Java)로 푸는 지게차와 크레인 문제 - 프로그래머스 🚜🏗️

---

🔎 문제 개요

프로그래머스 - 지게차와 크레인 문제입니다.
창고(storage)의 상태가 주어지고,
크레인과 지게차의 요청(requests)이 순서대로 주어질 때,
모든 요청이 처리된 후 창고에 남아있는 컨테이너 개수를 구하는 문제입니다.

🔹 요청 처리 방식

1️⃣ 크레인 사용 요청: 창고에 있는 특정 컨테이너를 모두 제거
2️⃣ 지게차 이동 요청: 해당 컨테이너가 창고 외부와 연결되어 있다면 제거

---

💡 예제 입력

String[] storage = {
    "AAB",
    "ABB",
    "AAB"
};

String[] requests = {
    "A",  // 크레인: 'A' 컨테이너 모두 제거
    "B-"  // 지게차: 'B' 컨테이너 중 외부와 연결된 것 제거
};

💡 예제 출력

1

➡ 최종적으로 창고에 남아있는 컨테이너 개수는 1개

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 BFS(너비 우선 탐색) + 시뮬레이션을 활용합니다.

✏️ 주요 고려 사항

✔ 크레인 요청(A)은 해당 컨테이너를 전부 제거
✔ 지게차 요청(B-)은 해당 컨테이너가 창고 외부와 연결된 경우만 제거
✔ BFS를 활용하여 외부와 연결된 컨테이너를 탐색
✔ 모든 요청이 끝난 후 창고에 남아있는 컨테이너 개수를 반환

---

🔹 Java 코드 해설

import java.util.*;

class Solution {
    
    class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    boolean[][] check;
    char[][] board;
    int N, M;
    int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int solution(String[] storage, String[] requests) {
        N = storage.length;
        if (N == 0) return 0;
        M = storage[0].length();

        // 모든 배열을 N+2 x M+2 크기로 생성 (패딩 추가)
        check = new boolean[N + 2][M + 2];
        board = new char[N + 2][M + 2];

        // 창고 내부 정보 저장 (1,1)부터 (N,M)까지
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                board[i][j] = storage[i - 1].charAt(j - 1);
            }
        }

        for (String request : requests) {
            char target = request.charAt(0);

            if (request.length() == 2) {  // 크레인 사용 (모든 해당 컨테이너 제거)
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= M; j++) {
                        if (board[i][j] == target) {
                            board[i][j] = '-';
                        }
                    }
                }
            } else {  // 지게차 이동 (외부와 연결된 컨테이너만 제거)
                BFS(target);
            }
        }

        // 최종적으로 남아있는 컨테이너 개수 세기
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (board[i][j] != '-') {
                    answer++;
                }
            }
        }
        return answer;
    }

    public void BFS(char target) {
        boolean[][] isVisited = new boolean[N + 2][M + 2];
        Queue<Node> q = new ArrayDeque<>();

        // 창고 외부(가장자리)에서 BFS 시작
        for (int i = 0; i <= N + 1; i++) {
            q.add(new Node(i, 0)); // 왼쪽 벽
            q.add(new Node(i, M + 1)); // 오른쪽 벽
            isVisited[i][0] = isVisited[i][M + 1] = true;
        }
        for (int j = 0; j <= M + 1; j++) {
            q.add(new Node(0, j)); // 위쪽 벽
            q.add(new Node(N + 1, j)); // 아래쪽 벽
            isVisited[0][j] = isVisited[N + 1][j] = true;
        }

        while (!q.isEmpty()) {
            Node cur = q.poll();

            for (int d = 0; d < 4; d++) {
                int dx = cur.x + dir[d][0];
                int dy = cur.y + dir[d][1];

                // 창고 범위 (0,0) ~ (N+1, M+1)
                if (dx < 0 || dx > N + 1 || dy < 0 || dy > M + 1) continue;
                if (isVisited[dx][dy]) continue;

                if (board[dx][dy] == target) {  // 요청된 컨테이너 제거
                    board[dx][dy] = '-';
                    isVisited[dx][dy] = true;
                } else if (board[dx][dy] == '-') { // 빈 공간이면 계속 탐색
                    check[dx][dy] = false;
                    q.add(new Node(dx, dy));
                    isVisited[dx][dy] = true;
                }
            }
        }
    }
}

---

🔍 코드 설명

📌 1. 창고 정보 초기화

board = new char[N + 2][M + 2]; // 패딩 추가

• 창고를 2칸씩 확장하여 board[N+2][M+2] 크기로 설정

---

📌 2. 크레인 요청 처리

if (request.length() == 2) {  // 크레인 사용
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (board[i][j] == target) {
                board[i][j] = '-';
            }
        }
    }
}

• 창고 전체를 순회하며 해당 컨테이너를 모두 제거

---

📌 3. 지게차 요청 처리 (BFS)

public void BFS(char target) {
    boolean[][] isVisited = new boolean[N + 2][M + 2];
    Queue<Node> q = new ArrayDeque<>();

    // 창고 외부(가장자리)에서 BFS 시작
    for (int i = 0; i <= N + 1; i++) {
        q.add(new Node(i, 0)); q.add(new Node(i, M + 1));
        isVisited[i][0] = isVisited[i][M + 1] = true;
    }
    for (int j = 0; j <= M + 1; j++) {
        q.add(new Node(0, j)); q.add(new Node(N + 1, j));
        isVisited[0][j] = isVisited[N + 1][j] = true;
    }

    while (!q.isEmpty()) {
        Node cur = q.poll();

        for (int d = 0; d < 4; d++) {
            int dx = cur.x + dir[d][0];
            int dy = cur.y + dir[d][1];

            if (board[dx][dy] == target) {
                board[dx][dy] = '-';
                isVisited[dx][dy] = true;
            }
        }
    }
}

• 외부와 연결된 컨테이너만 제거

---

🏆 정리

✅ 핵심 포인트

✔ 크레인은 창고 전체 탐색 후 제거
✔ 지게차는 BFS를 사용하여 외부 연결 컨테이너만 제거
✔ O(NM)의 시간 복잡도로 최적화된 탐색 가능

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊