[Programmers] 지게차와 크레인 JAVA

반응형

728x90

[Programmers] 지게차와 크레인 - LV 2

---

접근

• dfs

---

풀이

코드챌린지 1차 예선의 3번째 문제 지게차와 크레인 문제이다. 컨테이너가 배열로 주어지고 지게차와 크레인을 사용해 컨테이너를 꺼내고 난 뒤 남아있는 컨테이너의 개수를 반환하는 문제이다. 간단한데 헷갈리는 부분이 있어 헤맸던 문제이다.

 

크레인은 단순히 요청하는 컨테이너를 모두 제거하면 되기 때문에 간단한 작업이다. 문제는 지게차를 이용한 작업으로 지게차로 컨테이너를 제거하기 위해서는 컨테이너의 4면 중 한 면이 외부와 연결되어 있어야 한다. 단순히 컨테이너의 4면 중 한 면이 공백과 닿아있는 것이 아니라 그 공백이 외부와 닿아있어야 한다는 것이 중점이다. 

 

또 다른 주의 사항인 지게차 작업에만 해당되는 내용으로 작업이 수행되는 request의 한 라운드 즉 A라는 컨테이너를 지게차로 꺼내야 하는 경우 작업이 시작되기 전 외부와 닿아있는 컨테이너만 해당 라운드에 꺼낼 수 있다. 이 말은 지게차 작업을 진행하면서 생긴 공백으로 외부와 닿게 되는 컨테이너가 새로 생긴다면 해당 컨테이너도 같이 제거하는 것이 아닌 작업 시작 전 닿아있던 컨테이너만 제거한다는 뜻이다. 

 

위의 두 가지 주의 사항을 잘 고려해야 올바른 답을 얻어낼 수 있다.

class Solution {
    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};
    
    public int solution(String[] storage, String[] requests) {
        char[][] containers = new char[storage.length][];

        for (int i = 0; i < storage.length; i++) {
            containers[i] = storage[i].toCharArray();
        }

        for (String request : requests) {
            char c = request.charAt(0);

            if (request.length() == 1) {
                removeWithForklift(containers, c);
            } else {
                removeWithCrane(containers, c);
            }

        }

        int count = 0;

        for (char[] container : containers) {
            for (char c : container) {
                if (c != 0) {
                    count++;
                }
            }
        }
        return count;
    }

메인 메서드의 부분으로 컨테이너를 char 2차원 배열로 변경하여 관리해 줬고 요청 작업이 지게차인지 크레인인지 구분하여 각 작업을 수행해 준 뒤 남아있는 컨테이너의 개수를 세어 반환했다. 컨테이너를 제거할 때마다 해당 위치의 값을 0으로 변경해 줬고 작업이 지게차인지 크레인인지는 요청의 길이를 토대로 구분해 줬다. 

    private void removeWithCrane(char[][] containers, char c) {
        for (int i = 0; i < containers.length; i++) {
            for (int j = 0; j < containers[i].length; j++) {
                if (containers[i][j] == c) {
                    containers[i][j] = 0;
                }
            }
        }
    }

크레인을 통한 작업으로 위에서 모든 컨테이너를 다 뽑아내기 때문에 단순히 루프를 돌며 해당하는 컨테이너를 다 제거해 주면 되는 간단한 내용이다.

    private void removeWithForklift(char[][] containers, char c) {
        boolean[][] isVisited = new boolean[containers.length][containers[0].length];

        for (int i = 0; i < containers.length; i++) {
            for (int j = 0; j < containers[i].length; j++) {
                if ((i == 0 || j == 0 || i == containers.length - 1 || j == containers[i].length - 1)
                        && !isVisited[i][j]) {
                    dfs(containers, i, j, c, isVisited);
                }
            }
        }
        
        for (int i = 0; i < containers.length; i++) {
            for (int j = 0; j < containers[i].length; j++) {
                if (containers[i][j] == 1) {
                    containers[i][j] = 0;
                }
            }
        }
    }

문제의 지게차 작업 내용이다. dfs를 사용해서 4면의 외곽에서부터 제거 가능한 컨테이너를 찾도록 했다. 외곽에서 dfs를 시작하지 않는다면 크레인으로 제거하고 생긴 가운데 공백에서 잘못된 처리를 수행할 수 있기 때문에 외곽에서 출발시켜 확실하게 외부와 닿아있는 컨테이너만 제거할 수 있게 해주는 것이다. 작업이 끝나면 마킹된 컨테이너를 빼주게 되는데 두 번째 주의 사항 때문에 dfs를 돌며 컨테이너를 실제로 제거하지 않고 마킹해 둔 컨테이너를 작업이 끝난 후 제거하는 부분이다.

    private void dfs(char[][] containers, int x, int y, char c, boolean[][] isVisited) {
        if (x < 0 || y < 0 || x >= containers.length || y >= containers[x].length 
                || isVisited[x][y]) {
            return;
        }

        isVisited[x][y] = true;

        if (containers[x][y] == c) {
            containers[x][y] = 1;
            return;
        }
        
        if(containers[x][y] != 0) return;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            dfs(containers, nx, ny, c, isVisited);
        }
    }

dfs코드로 좌표가 배열의 범위 밖인 경우 종료시켜 주고 현재 컨테이너가 찾고자 하는 컨테이너라면 마킹을 한 뒤 종료 시킨다. 여기서 헷갈릴 수 있는 게 dfs가 수행되는 조건은 현재 좌표에 컨테이너가 없는 즉 값이 0인 상태에만 계속 수행이 되어야 한다. 종료 조건으로는

1. 찾고자 하는 컨테이너를 발견

2. 다른 컨테이너를 발견

위 두 가지로 현재 좌표에 어떤 컨테이너라도 존재한다면 더 이상 탐색을 진행하지 않아야 한다. 그렇기 때문에 1로 마킹된 컨테이너와 다른 컨테이너를 제외한, 공백이 아닌 무언가가 존재한다면 탐색을 종료해주어야 한다. 

---

전체 코드

import java.util.*;

class Solution {
    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};
    
    public int solution(String[] storage, String[] requests) {
        char[][] containers = new char[storage.length][];

        for (int i = 0; i < storage.length; i++) {
            containers[i] = storage[i].toCharArray();
        }

        for (String request : requests) {
            char c = request.charAt(0);

            if (request.length() == 1) {
                removeWithForklift(containers, c);
            } else {
                removeWithCrane(containers, c);
            }

        }

        int count = 0;

        for (char[] container : containers) {
            for (char c : container) {
                if (c != 0) {
                    count++;
                }
            }
        }
        return count;
    }

    private void removeWithCrane(char[][] containers, char c) {
        for (int i = 0; i < containers.length; i++) {
            for (int j = 0; j < containers[i].length; j++) {
                if (containers[i][j] == c) {
                    containers[i][j] = 0;
                }
            }
        }
    }

    private void removeWithForklift(char[][] containers, char c) {
        boolean[][] isVisited = new boolean[containers.length][containers[0].length];

        for (int i = 0; i < containers.length; i++) {
            for (int j = 0; j < containers[i].length; j++) {
                if ((i == 0 || j == 0 || i == containers.length - 1 || j == containers[i].length - 1)
                        && !isVisited[i][j]) {
                    dfs(containers, i, j, c, isVisited);
                }
            }
        }
        
        for (int i = 0; i < containers.length; i++) {
            for (int j = 0; j < containers[i].length; j++) {
                if (containers[i][j] == 1) {
                    containers[i][j] = 0;
                }
            }
        }
    }

    private void dfs(char[][] containers, int x, int y, char c, boolean[][] isVisited) {
        if (x < 0 || y < 0 || x >= containers.length || y >= containers[x].length 
                || isVisited[x][y]) {
            return;
        }

        isVisited[x][y] = true;

        if (containers[x][y] == c) {
            containers[x][y] = 1;
            return;
        }
        
        if(containers[x][y] != 0) return;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            dfs(containers, nx, ny, c, isVisited);
        }
    }
}