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

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

프로그래머스

 

문제 설명

A 회사의 물류창고에는 알파벳 대문자로 종류를 구분하는 컨테이너가 세로로 n 줄, 가로로 m줄 총 n x m개 놓여 있습니다. 특정 종류 컨테이너의 출고 요청이 들어올 때마다 지게차로 창고에서 접근이 가능한 해당 종류의 컨테이너를 모두 꺼냅니다. 접근이 가능한 컨테이너란 4면 중 적어도 1면이 창고 외부와 연결된 컨테이너를 말합니다.

최근 이 물류 창고에서 창고 외부와 연결되지 않은 컨테이너도 꺼낼 수 있도록 크레인을 도입했습니다. 크레인을 사용하면 요청된 종류의 모든 컨테이너를 꺼냅니다.

 

위 그림처럼 세로로 4줄, 가로로 5줄이 놓인 창고를 예로 들어보겠습니다. 이때 "A", "BB", "A" 순서대로 해당 종류의 컨테이너 출고 요청이 들어왔다고 가정하겠습니다. “A”처럼 알파벳 하나로만 출고 요청이 들어올 경우 지게차를 사용해 출고 요청이 들어온 순간 접근 가능한 컨테이너를 꺼냅니다. "BB"처럼 같은 알파벳이 두 번 반복된 경우는 크레인을 사용해 요청된 종류의 모든 컨테이너를 꺼냅니다.

 

위 그림처럼 컨테이너가 꺼내져 3번의 출고 요청 이후 남은 컨테이너는 11개입니다. 두 번째 요청은 크레인을 활용해 모든 B 컨테이너를 꺼냈음을 유의해 주세요. 세 번째 요청이 들어왔을 때 2행 2열의 A 컨테이너만 접근이 가능하고 2행 3열의 A 컨테이너는 접근이 불가능했음을 유의해 주세요.

처음 물류창고에 놓인 컨테이너의 정보를 담은 1차원 문자열 배열 storage와 출고할 컨테이너의 종류와 출고방법을 요청 순서대로 담은 1차원 문자열 배열 requests가 매개변수로 주어집니다. 이때 모든 요청을 순서대로 완료한 후 남은 컨테이너의 수를 return 하도록 solution 함수를 완성해 주세요.

 

접근 방법

일단 이 문제를 푸는데 하루가 넘게 걸렸다. 다른 사람들과 비슷하게 풀었고, 크레인 요청일 때는 단순하게 일치하는 값을 제거하면 됐지만 지게차 요청인 경우가 문제였다.

 

외부에서 접근할 때만 컨테이너를 삭제해줘야 하는데, 나의 코드 상으론 내부까지 삭제시켜주고 있었다.

 

안쪽에 있는 삭제된 칸의 경우, `내부에 있는 칸` 이므로 접근할 수 없다. 하지만, 내 로직으로 저 칸도 접근 가능했기 때문에 중간에 있는 `A`까지 삭제시켜주었다.

 

결론적으로, 외부에 있는 컨테이너와 내부에 있는 컨테이너를 구분할 로직이 필요했다. 

 

해결 방법

다른 사람의 코드를 참고한 뒤에야, 해결할 수 있었다. 

주요 로직은 이러했다.

 

1. 가장 자리들을 순회하면서, 빈칸이거나 방문하지 않은 경우 큐에 해당 좌표를 넣어주고, 방문처리를 해준다.
2. 큐를 순회하면서, 현재 좌표에서 동서남북으로 이동했을 때 컨테이너가 삭제됐고, 방문되지 않은 경우(외부와 연결되지 않은 경우)에만 다시 큐에 넣어 탐색을 이어 나간다. -> 
3. 2차원 배열을 순회하면서, 현재 좌표가 삭제시켜줘야 할 컨테이너와 같을 때를 체크한다.
   1. 만약에 현재 좌표가 가장자리라면, 컨테이너를 삭제처리 해준다.
   2. 인접한 칸이 삭제됐고, 방문처리가 된 경우 (외부와 연결된 경우)에 컨테이너를 삭제 처리해준다. 

 

 

로직이 이렇게 될 때, 흐름을 살펴보면

 

처음에 가장자리를 탐색할 때 컨테이너들이 삭제되지 않았으므로, 1,2 로직이 실행되지 않는다. 

2차원 배열만 돌면서 가장자리에 있는 컨테이너들만 삭제처리, `'.'` 으로 바꿔준다.

 

 

크레인으로 컨테이너를 삭제할 때는 동일한 값만 삭제처리 해주면 된다.

 

 

 

마지막으로 3번째 요청을 보자.

 

처음에 당연히 가장자리 삭제된 `A` 좌표들을 큐에 넣고 돌린다.

BFS를 돌면서 다음 탐색지점을 살펴보는데, 컨테이너가 삭제되었고 외부와 연결되지 않은 좌표들을 다시 넣어준다. 

(이 때 외부와 연결되었다는 visited[x][y] = true 표시를 해줘야 한다.)

 

이 때, 삭제된 B의 좌표들을 넣어주는데 당연하게도 안쪽의 `삭제된 B 좌표`는 도달할 수 없으므로 탐색이 불가능하다.

 

따라서, 삭제된 B의 좌표들에서 출발하면서 `A`와 같고 외부와 연결되지 않은 좌표를 탐색하다 보면 자연스럽게 `A` 하나만 삭제된다.

 

정답 코드

import java.util.*;

class Solution {
    char [][] board;
    int n, m;
    int [] dx = {1,0,-1,0};
    int [] dy = {0,1,0,-1};

    public int solution(String[] storage, String[] requests) {
        int answer = 0;
        n = storage.length;
        m = storage[0].length();
        
        board = new char[n][m];

        for(int i = 0; i < n; i++){
            String str = storage[i];
            for(int j = 0; j < m; j++) {
                board[i][j] = str.charAt(j);
            }
        }
        
        for(int i = 0; i < requests.length; i++) {
            String request = requests[i];
            char target = request.charAt(0);
            if (request.length() == 1) {
                jigae(target);
            }
            else crane(target);
            
            
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (board[i][j] != '.') answer++;
                //System.out.print(board[i][j]);
            }
            //System.out.println();
        }
        return answer;
    }
    
    public void jigae(char target) {
        boolean [][] visited = new boolean[n][m];
        Queue<int []> q = new LinkedList<>();
        
        for(int i = 0; i < n; i++) {
            if (board[i][0] == '.' && !visited[i][0]) {
                visited[i][0] = true;
                q.add(new int[]{i,0});
            }
            if (board[i][m-1] == '.' && !visited[i][m-1]) {
                visited[i][m-1] = true;
                q.add(new int[]{i,m-1});
            }
        }
        
        for(int i = 0; i < m; i++) {
            if (board[0][i] == '.' && !visited[0][i]) {
                visited[0][i] = true;
                q.add(new int[]{0,i});
            }
            if (board[n-1][i] == '.' && !visited[n-1][i]) {
                visited[n-1][i] = true;
                q.add(new int[]{n-1, i});
            }
        }
        
        while(!q.isEmpty()) {
            int [] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            for(int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (board[nx][ny] == '.' && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx,ny});
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (board[i][j] == target) {
                    boolean isAccessible = false;
                    for(int dir = 0; dir < 4; dir++) {
                        int nx = i + dx[dir];
                        int ny = j + dy[dir];
                        
                        // 가장자리 인 경우는 당연히 접근 가능
                        if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                            isAccessible = true;
                            break;
                        }
                        
                        // 인접칸이 빈칸이면서, 외부와 연결된 경우 접근 가능
                        if (board[nx][ny] == '.' && visited[nx][ny]) {
                            isAccessible = true;
                            break;
                        }
                    }
                    
                    // 접근 가능한 경우, 빈칸으로 만들어준다. 
                    if (isAccessible) {
                        board[i][j] = '.';
                    }
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                // if (board[i][j] != '.') answer++;
                System.out.print(visited[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    
    public void crane(char target) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (board[i][j] == target) board[i][j] = '.';
            }
        }
    }
}