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

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/388353#qna

프로그래머스

---

문제 풀이

요청 requests의 문자열의 길이가 1이면 지게차로, 2면 크레인으로 컨테이너를 꺼내야 한다.

 

1. 크레인 : 크레인의 로직은 간단하다. 모든 배열을 순회하며 동일한 문자열의 컨테이너를 모두 뽑으면 된다.

2. 지게차 : 지게차의 경우, 외부와 닿아있는 컨테이너만 뽑을 수 있기에 주의해야 한다.

 

+ 지게차 구현에서 시간이 오래 걸렸던 문제이다.

 

 

 

 

arr에 찾는 컨테이너를 발견할 경우, 1로 마킹해두고 바로 뽑지 않는 이유

        // dfs가 끝난 후 '1'로 마킹해놓았던 컨테이너를 뽑아줌
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(arr[i][j] == 1) {
                    arr[i][j] = 0;
                }
            }
        }

-> 발견 즉시 컨테이너를 뽑을 경우, 외부와 연결되지 않은 컨테이너도 뽑아버릴 수 있음 주의..

 

 

 

import java.util.*;

class Solution {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static char[][] arr;
    static int N;
    static int M;
    
    public int solution(String[] storage, String[] requests) {
        int answer = 0;
        
        N = storage.length;
        M = storage[0].length();
        arr = new char[N][M];
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                arr[i][j] = storage[i].charAt(j);
            }
        }
        
        for(String reqStr : requests) {
            char req = reqStr.charAt(0);
            if(reqStr.length() == 1) {
                // 지게차
                jiga(req);          
            } else {
                // 크레인
                crain(req);
            }
        }
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(arr[i][j] != 0) {
                    // System.out.println("i, j ->" + i + ", " + j);

                    answer++;
                }
            }
        }
        return answer;
    }
    
    private void jiga(char req) {
        visited = new boolean[N][M];
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                // 테두리에서부터 탐색 시작 -> 외부랑 연결된 컨테이너만 제거할 수 있도록
                if(isBoundary(i, j) && !visited[i][j]) {
                    dfs(i, j, req, visited);
                }
            }
        }
        
        // dfs가 끝난 후 '1'로 마킹해놓았던 컨테이너를 뽑아줌
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(arr[i][j] == 1) {
                    arr[i][j] = 0;
                }
            }
        }
    }
    
    private void dfs(int x, int y, char c, boolean[][] visited) {
        if(x<0 || y<0 || x>=N || y>=M || visited[x][y]) {
            return;
        }
        
        visited[x][y] = true;
        
        // 현재 찾는 컨테이너라면 일단 '1'로 표시
        if(arr[x][y] == c) {
            arr[x][y] = 1;
            return;
        }
        
        // 컨테이너가 이미 뽑힌 상태에서만 dfs가 수행되어야 함
        if(arr[x][y] != 0) {
            return;
        }
        
        for(int k=0; k<4; k++) {
            int nextX = x + dx[k];
            int nextY = y + dy[k];
            dfs(nextX, nextY, c, visited);
        }
    }
    
    private void crain(char c) {
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(arr[i][j] == c) {
                    arr[i][j] = 0; // 일치하는 문자열이 있으면 모두 뽑음
                }
            }
        }
    }
    
    // 바같과 연결된 좌표 리턴
    private boolean isBoundary(int x, int y) {
        boolean flag = false;
        if(x == 0 || y == 0 || x == N-1 || y == M-1) {
            // 테두리에 있다면
            return true;
        } else {
            return false;
        }
    }
}