[프로그래머스] 지게차와 크레인 (Java) — BFS

📌 핵심 요약

• BFS의 출발점은 외부 — 격자 안의 임의 칸이 아니라 창고 바깥에서 빈칸('.')을 타고 퍼진다. 도달한 빈칸 영역에 인접한 target 컨테이너가 지게차로 꺼낼 수 있는 컨테이너다.
• 판정과 반영의 분리 — 접근 가능 판정은 요청 시점의 상태 기준이다. BFS 도중 제거하면 같은 요청에서 연쇄 제거가 일어나므로, removeList에 기록만 하고 BFS 종료 후 한꺼번에 반영한다.
• 패딩 vs 무패딩 — 패딩은 외부에 좌표를 부여해 시작점을 하나로 만들고 가장자리 특수 케이스를 없앤다. 무패딩은 좌표 보정이 없는 대신 멀티 소스 BFS와 테두리 target 즉시 제거 처리가 필요하다.

 

목차

1 문제 이해

Programmers #388353

지게차와 크레인

2 ≤ n, m ≤ 50 · requests ≤ 100

난이도: Lv. 2

n × m 창고에 알파벳 대문자로 구분되는 컨테이너가 놓여 있다. 요청이 "A"처럼 한 글자면 지게차로 접근 가능한 해당 종류 컨테이너를 모두 꺼내고, "BB"처럼 두 글자면 크레인으로 해당 종류를 전부 꺼낸다. 접근 가능하다는 것은 4면 중 적어도 1면이 창고 외부와 연결되어 있다는 뜻이다. 모든 요청 수행 후 남은 컨테이너 수를 구한다.

풀이 과정

1. 크레인 요청은 격자 전체를 순회하며 해당 종류를 모두 '.'로 바꾼다.
2. 지게차 요청은 외부에서 출발하는 BFS로 외부와 연결된 빈칸 영역을 확정한다.
3. 그 영역에 인접한 target 컨테이너를 기록해두고, BFS 종료 후 한꺼번에 제거한다.
4. 모든 요청 후 '.'이 아닌 칸을 세어 반환한다.

크레인은 단순 전체 순회로 끝난다. 이 문제의 본체는 지게차의 "접근 가능" 판정이고, 이는 "이 빈칸이 창고 외부와 연결되어 있는가"라는 연결성 문제이므로 BFS가 정석이다.

2 접근 — BFS의 방향

처음에는 격자의 (0, 0)에서 BFS를 시작하는 뼈대를 잡았다. 하지만 (0, 0)은 컨테이너일 수도 있는 임의의 칸이고, 알고 싶은 것은 그 칸이 아니라 "외부에서 어디까지 들어올 수 있는가"이다. 따라서 출발점은 격자 안의 어떤 칸이 아니라 창고 바깥이어야 한다.

💡

BFS는 외부에서 안쪽으로

외부에서 빈칸('.')을 타고 퍼지는 BFS를 돌리면 도달한 빈칸들이 곧 "외부와 연결된 공간"이 된다. 그 공간에 한 면이라도 닿아 있는 target 컨테이너가 지게차로 꺼낼 수 있는 컨테이너다. BFS는 빈칸만 통로로 쓰고, target은 기록만 하며, 다른 알파벳은 벽으로 취급한다.

또 하나의 핵심은 동시성이다.

지게차 요청 하나에서 접근 가능 판정은 요청 시점의 상태 기준이다. 바깥쪽 컨테이너를 꺼냈다고 해서 그로 인해 뚫린 안쪽 컨테이너가 같은 요청에서 연달아 나가면 안 된다.

예제 1의 세 번째 요청이 정확히 이 케이스로, 2행 2열의 A만 나가고 2행 3열의 A는 남아야 한다.

ℹ️

판정은 요청 시점 상태로, 반영은 마지막에

BFS 도중 target을 즉시 '.'로 바꾸면 그 자리가 통로가 되어 안쪽 target까지 연쇄로 제거된다. removeList에 좌표만 기록해두고 BFS가 완전히 끝난 뒤 한꺼번에 '.'로 바꾸면 이 문제가 사라진다. 상태 변경 타이밍을 의도적으로 통제하는 패턴이다.

3 풀이 1 — 패딩 BFS

패딩 트릭

"외부"는 격자 밖이라 좌표가 없다. 그래서 격자를 상하좌우 한 겹씩 '.'로 감싸 (N+2) × (M+2)로 만들었다.

외부가 실제 좌표를 가진 빈칸이 되므로 패딩의 (0, 0)에서 BFS를 시작하면 테두리를 따라 전부 연결되어 자연스럽게 외부 영역이 완성된다. 가장자리 컨테이너도 패딩 빈칸과 인접하게 되므로 특별 취급 없이 같은 로직으로 처리된다. 대신 원본 좌표가 전부 +1씩 밀리므로 크레인 루프와 카운트 루프의 범위는 1 ~ N, 1 ~ M이다.

 

Java — 풀이 1: 패딩 BFS

import java.util.*;

class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    int N, M;

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

        // 패딩: 상하좌우 한 겹을 '.'로 감싼 (N+2) x (M+2) 맵
        char[][] map = new char[N + 2][M + 2];
        for (char[] row : map) Arrays.fill(row, '.');
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i + 1][j + 1] = storage[i].charAt(j);
            }
        }

        for (String s : requests) {
            char target = s.charAt(0);
            if (s.length() == 2) {
                // 크레인: 전부 제거
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= M; j++) {
                        if (map[i][j] == target) map[i][j] = '.';
                    }
                }
            } else {
                bfs(map, target);
            }
        }

        // 남은 컨테이너 개수
        int remain = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] != '.') remain++;
            }
        }
        return remain;
    }

    private void bfs(char[][] map, char target) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[map.length][map[0].length];
        List<int[]> removeList = new ArrayList<>();

        queue.add(new int[]{0, 0});   // 패딩의 (0,0) = 외부
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = cur[0] + dx[i];
                int nextY = cur[1] + dy[i];

                // 경계 검사와 방문 검사는 독립된 두 줄로
                if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) continue;
                if (visited[nextX][nextY]) continue;

                if (map[nextX][nextY] == '.') {
                    visited[nextX][nextY] = true;
                    queue.add(new int[]{nextX, nextY});
                } else if (map[nextX][nextY] == target) {
                    visited[nextX][nextY] = true;   // 중복 등록 방지
                    removeList.add(new int[]{nextX, nextY});
                }
                // 다른 알파벳 컨테이너: 벽 취급
            }
        }

        // 동시 제거: BFS가 끝난 뒤 한꺼번에
        for (int[] p : removeList) {
            map[p[0]][p[1]] = '.';
        }
    }
}

4 풀이 2 — 무패딩 멀티 소스 BFS

패딩 없이 N × M 배열 그대로 푸는 방법도 정리했다.

패딩이 공짜로 해결해주던 두 가지를 직접 처리하면 된다.

첫째, BFS 시작점이 하나가 아니라 여러 개가 된다(멀티 소스 BFS). 외부와 직접 닿아 있는 것은 격자의 테두리 칸들이므로, 테두리를 순회하며 '.'인 칸을 전부 큐에 넣고 시작한다. 테두리의 빈칸들은 중간에 컨테이너로 끊겨 서로 떨어져 있을 수 있으므로 하나만 넣으면 안 된다.

둘째, 테두리에 있는 target 컨테이너는 BFS와 무관하게 즉시 제거 대상이다. 테두리 칸은 그 자체로 한 면이 외부와 닿아 있어 빈칸을 경유할 필요가 없다. 패딩 버전에서는 패딩 '.'가 이 판정을 대신해줬지만, 무패딩에서는 테두리 순회 때 직접 체크해야 한다.

 

Java — 풀이 2: 무패딩 멀티 소스 BFS

import java.util.*;

class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    int N, M;

    public int solution(String[] storage, String[] requests) {
        N = storage.length;
        M = storage[0].length();
        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = storage[i].toCharArray();
        }

        for (String s : requests) {
            char target = s.charAt(0);
            if (s.length() == 2) {
                // 크레인: 전부 제거
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (map[i][j] == target) map[i][j] = '.';
                    }
                }
            } else {
                bfs(map, target);
            }
        }

        int remain = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != '.') remain++;
            }
        }
        return remain;
    }

    private void bfs(char[][] map, char target) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        List<int[]> removeList = new ArrayList<>();

        // 테두리 순회: '.'는 BFS 출발점, target은 즉시 제거 대상
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (i != 0 && i != N - 1 && j != 0 && j != M - 1) continue; // 테두리만
                if (visited[i][j]) continue;

                if (map[i][j] == '.') {
                    visited[i][j] = true;
                    queue.add(new int[]{i, j});
                } else if (map[i][j] == target) {
                    visited[i][j] = true;
                    removeList.add(new int[]{i, j});   // 한 면이 외부와 직접 연결
                }
            }
        }

        // 이후는 패딩 버전과 동일
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d];
                int ny = cur[1] + dy[d];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (visited[nx][ny]) continue;

                if (map[nx][ny] == '.') {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                } else if (map[nx][ny] == target) {
                    visited[nx][ny] = true;
                    removeList.add(new int[]{nx, ny});
                }
            }
        }

        for (int[] p : removeList) {
            map[p[0]][p[1]] = '.';
        }
    }
}

solution 쪽은 패딩 관련 코드가 빠지므로 오히려 단순해진다. storage를 그대로 맵에 넣고, 크레인/카운트 루프도 0 ~ N-1 범위로 돈다. 복잡함이 bfs 앞단의 테두리 처리로 옮겨간 셈이다.

5 두 풀이 비교 및 정리

구분	풀이 1: 패딩	풀이 2: 무패딩
맵 크기	(N+2) × (M+2)	N × M
BFS 시작점	하나 — 패딩의 (0, 0)	여러 개 — 테두리의 모든 '.'
가장자리 target	자동 처리 (패딩 '.'와 인접)	직접 처리 — 테두리 순회 시 즉시 제거 대상
좌표 보정	필요 — 원본 대비 +1	불필요
특수 케이스 수	0개 — 모든 판정이 하나의 규칙	1개 — 테두리 target 즉시 제거
성능/정답률	차이 없음 — 취향의 문제

로직 총량은 비슷하고, 복잡함이 어디에 놓이는지가 다르다.

패딩 버전은 좌표 +1 보정이라는 비용을 내는 대신 BFS가 단순해지고, 무패딩 버전은 좌표가 깔끔한 대신 BFS 앞단에 테두리 특수 처리가 붙는다.

나는 모든 판정이 "외부 영역 빈칸과 인접한가" 하나로 통일되는 패딩 쪽이 실수 여지가 적다고 판단했다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.