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

문제

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

프로그래머스

 

---

 

문제 개요

A 회사의 물류 창고에는 알파벳 대문자로 구분된 컨테이너가 세로 n 줄, 가로 m 줄로 총 n x m개가 놓여 있습니다. 특정 컨테이너 출고 요청이 들어오면 지게차 또는 크레인을 사용해 출고합니다.

• 지게차 사용 (알파벳 1개 요청): 창고 외부와 연결된 컨테이너만 출고 가능
• 크레인 사용 (알파벳 2개 요청): 해당 종류의 모든 컨테이너 출고

모든 요청을 수행한 후 남은 컨테이너 개수를 구하는 것이 목표입니다.

 

접근 방법

1. 입력 데이터 저장
   • storage를 2차원 배열(map)로 변환하여 관리
   • 요청(requests)을 순서대로 처리
2. 출고 방식 구현
   • 크레인 요청 (BB처럼 알파벳 2개 요청): 해당 알파벳을 가진 모든 컨테이너 제거
   • 지게차 요청 (A처럼 알파벳 1개 요청): 창고 외부와 연결된 컨테이너만 제거
     그림과 같이 한번의 요청에서 두 가지 A를 다 제거하지 않도록 주의 
     

     

     
     
    
3. 지게차 접근 가능 여부 확인
   • BFS(너비 우선 탐색)를 활용하여 컨테이너가 창고 외부와 연결되어 있는지 판별
4. 최종 남은 컨테이너 개수 계산
   • NONE으로 표시된 제거된 컨테이너를 제외한 개수 반환

 

코드

import java.util.*;
class Solution {
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static String[][] map;
    
    public int solution(String[] storage, String[] requests) {
        int answer = 0;
        
        makeMap(storage);
        for(String s : requests) {
            if(s.length() > 1) {
                crane(String.valueOf(s.charAt(0)));
            } else {
                car(s);
            }
        }
        
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[i].length; j++) {
                if(!map[i][j].equals("NONE")) answer++;
            }
        }
        
        return answer;
    }
    
    // 크레인: 모든 해당 컨테이너 제거
    public void crane(String target) {
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[i].length; j++) {
                if(map[i][j].equals(target)) {
                    map[i][j] = "NONE";
                }
            }
        }
    }
    
    // 지게차: 접근 가능한 컨테이너만 제거
    public void car(String target) {
        List<Pos> list = new ArrayList<>();
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[i].length; j++) {
                if(map[i][j].equals(target)) {
                    list.add(new Pos(i,j));
                }
            }
        }
        
        boolean[] checked = new boolean[list.size()];
        for(int i=0; i<list.size(); i++) {
            if(isPossible(list.get(i), target)) {
                checked[i] = true;
            }
        }
        
        for(int i=0; i<checked.length; i++) {
            if(checked[i]) {
                int r = list.get(i).r;
                int c = list.get(i).c;
                map[r][c] = "NONE";
            }
        }
    }
    
    // BFS로 접근 가능 여부 확인
    public boolean isPossible(Pos pos, String target) {
        boolean[][] v = new boolean[map.length][map[0].length];
        
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(pos.r, pos.c));
        v[pos.r][pos.c] = true;
        
        while(!q.isEmpty()) {
            Pos cur = q.poll();
            if(cur.r == 0 || cur.c == 0 || cur.r == map.length-1 || cur.c == map[0].length-1) return true;
            
            for(int i=0; i<4; i++) {
                int nr = dr[i] + cur.r;
                int nc = dc[i] + cur.c;
                
                if(nr >= 0 && nc >= 0 && nr < map.length && nc < map[0].length && !v[nr][nc] && map[nr][nc].equals("NONE")) {
                    v[nr][nc] = true;
                    q.add(new Pos(nr, nc));
                }
            }
        }
        
        return false;
    }
    
    // 2차원 배열 생성
    public void makeMap(String[] storage) {
        map = new String[storage.length][storage[0].length()];
        
        for(int i=0; i<map.length; i++) {
            map[i] = storage[i].split("");
        }
    }
    
    // 좌표 클래스
    class Pos {
        int r, c;
        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}