[programmers] 지게차와 크레인 (Python, Java풀이)

지게차로 겉에있는것을 꺼낼때만 주의하면된다.

패딩을 둘러준뒤 (0,0)부터 BFS상하좌우 빈칸들을 탐색한다.

이때 탐색칸이 빈칸이면 다음 탐색후보이기에,q에넣는다.

만약 target값이면 삭제가능하기에, 제거후보에 넣어준다.

전체 빈칸들 탐색이 끝나면, 제거후보들의 값을 모두삭제해준다.

 

순서를 정리하면 아래와같다.

 

1. 패딩 추가

• 그리드를 빈칸('')으로 둘러싸 (0,0)을 “외부 빈 공간”으로 만듦

2. BFS 탐색

• (0,0)에서 출발해 상·하·좌·우로 빈칸만 따라 들어감
• 빈칸이면 큐에 추가하여 계속 확산
• target 문자가 나오면 즉시 “제거 후보”에 기록(큐에는 넣지 않음)

3. 제거 수행

• BFS가 끝난 뒤, 기록된 모든 제거 후보 위치의 값을 빈칸('')으로 바꿔 삭제

 

 

편의상 0으로 빈공간 표기함:)

 

 

Python 풀이

from collections import deque

def solution(storage, requests):
    n, m = len(storage), len(storage[0])
    N, M = n+2, m+2

    # 1) 패딩
    pad_row = [''] * M
    middle  = [[''] + list(r) + [''] for r in storage]
    matrix  = [pad_row] + middle + [pad_row]

    dirs = [(-1,0),(1,0),(0,-1),(0,1)]

    # 2) 지게차
    def remove_by_forklift(target):
        visited = [[False]*M for _ in range(N)]
        q = deque([(0, 0)])
        visited[0][0] = True

        to_remove = set()

        while q:
            x, y = q.popleft()
            for dx, dy in dirs:
                nx, ny = x+dx, y+dy
                if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                    if matrix[nx][ny] == '':
                        visited[nx][ny] = True
                        q.append((nx, ny))
                    elif matrix[nx][ny] == target:
                        to_remove.add((nx, ny))
                        visited[nx][ny] = True

        for i, j in to_remove:
            matrix[i][j] = ''

    # 3) 크레인
    def remove_by_crane(target):
        for i in range(1, N-1):
            for j in range(1, M-1):
                if matrix[i][j] == target:
                    matrix[i][j] = ''

    # 4) 요청 처리
    for req in requests:
        if len(req) == 1:
            remove_by_forklift(req)
        else:
            remove_by_crane(req[0])

    # 5) 남은 개수 세기
    answer = 0
    for i in range(1, N-1):
        for j in range(1, M-1):
            if matrix[i][j] != '':
                answer += 1

    return answer

Java 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution  {
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static int N, M;
    static char[][] matrix;
    public int solution(String[] storage, String[] requests) {
        int n = storage.length;
        int m = storage[0].length();
        N = n + 2;
        M = m + 2;

        // 1) 패딩된 matrix 생성 ('.'은 빈 공간)
        matrix = new char[N][M];
        for (int i = 0; i < N; i++) {
            Arrays.fill(matrix[i], '.');
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i + 1][j + 1] = storage[i].charAt(j);
            }
        }
        // 2) 모든 요청 처리
        for (String req : requests) {
            char target = req.charAt(0);
            if (req.length() == 1) {
                removeByForklift(target);
            } else {
                removeByCrane(target);
            }
        }

        // 3) 남은 컨테이너 수 세기 (패딩 제외 영역)
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (matrix[i][j] != '.') {
                    answer++;
                }
            }
        }
        return answer;
    }

    private void removeByForklift(char target) {
        boolean[][] visited = new boolean[N][M];
        Queue<int[]> q = new LinkedList<>();
        List<int[]> toRemove = new ArrayList<>();

        // (0,0)에서 출발
        visited[0][0] = true;
        q.add(new int[]{0,0});

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y= cur[1];

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (visited[nx][ny]) continue;

                if (matrix[nx][ny] == '.') {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx,ny}); // 빈칸은 탐색후보로 지정
                } else if (matrix[nx][ny] == target) {
                    visited[nx][ny] = true;
                    toRemove.add(new int[]{nx,ny}); // 삭제후보에 추가
                }
            }
        }
        // 찍어둔 후보만 한 번에 제거
        for (int[] cell : toRemove) {
            matrix[cell[0]][cell[1]] = '.';
        }
    }

    // 크레인: target이 남아있는 모든 칸 제거
    private void removeByCrane(char target) {
        for (int i = 1; i < N - 1; i++){
            for (int j = 1; j < M - 1; j++) {
                if (matrix[i][j] == target)
                    matrix[i][j] = '.';
            }
        }
    }
}