[Grind75-LeetCode] Rotting Oranges JAVA

알고리즘/코딩테스트-Grind75

[Grind75-LeetCode] Rotting Oranges JAVA

kwang2134 2024. 11. 1. 16:15

728x90

[Grind75-LeetCode] Rotting Oranges - Medium

접근

풀이

썩은 오렌지 옆에 있는 오렌지는 1분이 지날 때마다 썩어가고 모든 오렌지가 다 썩기까지 걸리는 시간을 구하는 문제이다. 백준의 토마토 문제와 동일한 문제로 일이 분으로 각 과일의 상태를 나타내는 값이 조금씩 달라졌을 뿐 다른 게 없는 문제이다.

2024.09.29 - [알고리즘/코딩테스트-백준] - [백준] 토마토 JAVA

[백준] 토마토 JAVA

[백준] 토마토 - GOLD V 7579, 7576번7576번: 토마토 (acmicpc.net)7569번: 토마토 (acmicpc.net)접근bfs풀이토마토 농장에는 덜 익은 토마토와 다 익은 토마토가 존재하는데 덜 익은 토마토가 다 익은 토마토 옆

kwang2134.tistory.com

1차로 구현한 코드는 토마토 코드와 같으니 자세한 설명은 토마토 코드를 참고하자.

    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};

    private static class Orange {
        private final int x;
        private final int y;
        private final int mins;

        public Orange(int x, int y, int mins) {
            this.x = x;
            this.y = y;
            this.mins = mins;
        }
    }

토마토에서 오렌지로 바뀌고 days에서 mins로 변수명만 변경되었다.

    public int orangesRotting(int[][] grid) {
        Queue<Orange> que = new LinkedList<>();
        boolean[][] isVisited = new boolean[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    isVisited[i][j] = true;
                    que.offer(new Orange(i, j, 0));
                }
            }
        }

        int result = bfs(grid, que, isVisited);

        for (int[] ints : grid) {
            for (int anInt : ints) {
                if (anInt == 1) {
                    return -1;
                }
            }
        }

        return result;
    }

메인 함수로 Queue를 이용한 bfs를 사용하게 되는데 썩은 오렌지를 큐에 다 추가하고 bfs를 실행한다. bfs가 끝나면 배열을 한 번 더 체크해 썩지 않은 오렌지가 있는지 찾아보고 있다면 -1을 반환하게 된다.

    public int bfs(int[][] grid, Queue<Orange> que, boolean[][] isVisited) {
        int result = 0;

        while (!que.isEmpty()) {
            Orange orange = que.poll();
            int currentMins = orange.mins;
            result = Math.max(result, currentMins);

            for (int d = 0; d < 4; d++) {
                int nx = orange.x + dx[d];
                int ny = orange.y + dy[d];

                if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[nx].length || grid[nx][ny] == 0) {
                    continue;
                }

                if (isVisited[nx][ny]) {
                    continue;
                }

                que.offer(new Orange(nx, ny, currentMins + 1));
                isVisited[nx][ny] = true;
                grid[nx][ny] = 2;
            }

        }

        return result;
    }

bfs이다. bfs로 순회하다 보니 모든 좌표를 다 탐색했을 때 최대 mins를 결과로 반환하게 된다. 토마토 문제 코드와 같아 넘어가도록 하겠다.

백준에서 풀 땐 몰랐는데 이렇게 비교군이 생기다 보니 성능이 많이 떨어지는 것을 알게 되었다. 이 사이트에서 풀면서 내가 풀어왔던 코드들이 성능은 크게 고려를 안 했구나 라는 생각을 했지만 평균에 미치지 못하는 걸 보니 수정이 필요해 보였다.

성능 개선

보통 최근에 성능 개선을 했던 부분은 큐를 사용한 bfs 대신 재귀를 이용한 dfs로 푸는 방법이었다. 큐의 오버헤드를 줄이고자 하는 방법이었는데 그러나 이 문제는 모든 좌표를 한 번씩만 방문하면 되지만 썩어있는 오렌지들이 동시에 영향을 받기 때문에 깊이 있게 들어가는 dfs는 사용할 수 없다. 그렇기 때문에 코드를 수정해 성능을 개선해 봤다.

    public int orangesRotting(int[][] grid) {
        Queue<Orange> que = new LinkedList<>();
        int fresh = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    que.offer(new Orange(i, j, 0));
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }

        return bfs(grid, que, fresh);
    }

우선 방문 배열이 사라지고 fresh로 신선한 오렌지의 개수를 가진 변수를 추가했다. 신선한 오렌지 개수를 통해 작업 수행이 끝난 뒤 모든 오렌지가 썩었는지 여부를 바로 체크할 수 있다. 방문 배열의 경우 방문 했던 좌표의 중복을 방지하기 위해 사용했었는데 이미 오렌지가 상하면 원본 배열의 값을 2로 바꾸면서 굳이 없어도 되는 형태였다. 다음 좌표 값 조건 체크를 할 때 썩은 오렌지라면 건너뛰는 부분을 추가해 주면 끝이었다.

    public int bfs(int[][] grid, Queue<Orange> que, int fresh) {
        int result = 0;

        while (!que.isEmpty()) {
            Orange orange = que.poll();
            result = Math.max(result, orange.mins);

            for (int d = 0; d < 4; d++) {
                int nx = orange.x + dx[d];
                int ny = orange.y + dy[d];

                if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[nx].length || grid[nx][ny] != 1) {
                    continue;
                }

                grid[nx][ny] = 2;
                fresh--;
                que.offer(new Orange(nx, ny, orange.mins + 1));
            }

        }

        return fresh == 0 ? result : -1;
    }

변경된 bfs 코드이다. 범위를 체크하며 다음 좌표가 신선한 오렌지가 아닌 경우 건너뛰게 된다. 자연스레 공백이나 이미 썩은 오렌지를 중복 방문하지 않게 한다. 그리고 오렌지가 하나씩 썩을 때마다 신선한 오렌지 개수를 줄여주고 작업 수행이 끝난 뒤 모든 오렌지가 썩었는지 여부를 체크하고 반환한다.

3ms -> 2ms로 성능이 개선된 것을 볼 수 있다.

성능 개선2

1ms 코드를 참조한 방법으로 1분당 모든 오렌지에 대해 작업을 처리하고 다음으로 넘어가는 방식이었다.

    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        Queue<int[]> q = new LinkedList<>();
        int countFresh = 0;

        for(int i=0;i<grid.length;i++) {
            for(int j=0;j<grid[0].length;j++) {
                if(grid[i][j] == 2) q.add(new int[]{i,j});
                else if(grid[i][j] == 1) countFresh++;
            }
        }
        
        if(countFresh == 0) return 0;
        int count = 0;
        int dx[] = {0, 0, 1,-1};
        int dy[] = {1,-1, 0, 0};

처음 배열이 비어있는지 체크하는 조건이 있고 썩은 오렌지는 큐로 신선한 오렌지는 변수로 개수를 세는 과정은 동일하다. 그러나 큐에 들어가는 각 오렌지가 시간을 가지고 있지 않다. 만약 이미 신선한 오렌지가 없다면 종료한다.

        while(!q.isEmpty()) {
            ++count;
            int size = q.size();
            for(int i=0;i<size;i++) {
                int[] rottenPoint = q.poll();
                for(int j=0;j<4;j++) {
                    int x = rottenPoint[0] + dx[j];
                    int y = rottenPoint[1] + dy[j];
                    if(x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        q.add(new int[]{x,y});
                        countFresh--;
                    }
                }
            }
        }
        return countFresh == 0 ? count - 1 : -1;
    }
}

반복을 수행하는 부분이다. while문이 한 번 돌 때마다 count를 증가시켜 1분이 지났음을 체크한다. 그리고 현재 큐에 들어있는 모든 오렌지를 다 뽑아 처리하게 되는데 모든 오렌지가 1분동안 전파 시키는 것을 다 처리하고 다음 단계로 넘어가기 때문에 시간을 효율적으로 관리해 최댓값으로 업데이트 하는 등 불필요한 연산이 빠졌다.

전체 코드

bfs 토마토 코드 이식

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

    private static class Orange {
        private final int x;
        private final int y;
        private final int mins;

        public Orange(int x, int y, int mins) {
            this.x = x;
            this.y = y;
            this.mins = mins;
        }
    }

    public int orangesRotting(int[][] grid) {
        Queue<Orange> que = new LinkedList<>();
        boolean[][] isVisited = new boolean[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    isVisited[i][j] = true;
                    que.offer(new Orange(i, j, 0));
                }
            }
        }

        int result = bfs(grid, que, isVisited);

        for (int[] ints : grid) {
            for (int anInt : ints) {
                if (anInt == 1) {
                    return -1;
                }
            }
        }

        return result;
    }

    public int bfs(int[][] grid, Queue<Orange> que, boolean[][] isVisited) {
        int result = 0;

        while (!que.isEmpty()) {
            Orange orange = que.poll();
            int currentMins = orange.mins;
            result = Math.max(result, currentMins);

            for (int d = 0; d < 4; d++) {
                int nx = orange.x + dx[d];
                int ny = orange.y + dy[d];

                if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[nx].length || grid[nx][ny] == 0) {
                    continue;
                }

                if (isVisited[nx][ny]) {
                    continue;
                }

                que.offer(new Orange(nx, ny, currentMins + 1));
                isVisited[nx][ny] = true;
                grid[nx][ny] = 2;
            }

        }

        return result;
    }
}

성능 개선1

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

    private static class Orange {
        private final int x;
        private final int y;
        private final int mins;

        public Orange(int x, int y, int mins) {
            this.x = x;
            this.y = y;
            this.mins = mins;
        }
    }

    public int orangesRotting(int[][] grid) {
        Queue<Orange> que = new LinkedList<>();
        int freshCount = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    que.offer(new Orange(i, j, 0));
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }

        return bfs(grid, que, freshCount);
    }

    public int bfs(int[][] grid, Queue<Orange> que, int freshCount) {
        int result = 0;

        while (!que.isEmpty()) {
            Orange orange = que.poll();
            int currentMins = orange.mins;
            result = Math.max(result, currentMins);

            for (int d = 0; d < 4; d++) {
                int nx = orange.x + dx[d];
                int ny = orange.y + dy[d];

                if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[nx].length || grid[nx][ny] != 1) {
                    continue;
                }

                grid[nx][ny] = 2;
                freshCount--;
                que.offer(new Orange(nx, ny, orange.mins + 1));
            }

        }

        return freshCount == 0 ? result : -1;
    }
}

성능 개선2 - 1ms

class Solution {
    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        Queue<int[]> q = new LinkedList<>();
        int countFresh = 0;

        for(int i=0;i<grid.length;i++) {
            for(int j=0;j<grid[0].length;j++) {
                if(grid[i][j] == 2) q.add(new int[]{i,j});
                else if(grid[i][j] == 1) countFresh++;
            }
        }

        if(countFresh == 0) return 0;
        int count = 0;
        int dx[] = {0, 0, 1,-1};
        int dy[] = {1,-1, 0, 0};

        while(!q.isEmpty()) {
            ++count;
            int size = q.size();
            for(int i=0;i<size;i++) {
                int[] rottenPoint = q.poll();
                for(int j=0;j<4;j++) {
                    int x = rottenPoint[0] + dx[j];
                    int y = rottenPoint[1] + dy[j];
                    if(x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        q.add(new int[]{x,y});
                        countFresh--;
                    }
                }
            }
        }
        return countFresh == 0 ? count - 1 : -1;
    }
}

728x90

'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글

[Grind75-LeetCode] Combination Sum JAVA (0)	2024.11.03
[Grind75-LeetCode] Search in Rotated Sorted Array JAVA (0)	2024.11.02
[Grind75-LeetCode] Number of Islands JAVA (1)	2024.10.31
[Grind75-LeetCode] Validate Binary Search Tree JAVA (0)	2024.10.30
[Grind75-LeetCode] Min Stack JAVA (0)	2024.10.29

현재글[Grind75-LeetCode] Rotting Oranges JAVA

kwang2134 님의 블로그

개발/ 알고리즘/깃허브 https://github.com/kwang2134

leetcode, 티스토리챌린지, 코딩테스트, spring data JPA, BFS, 스프링, 웹 개발, 오블완, grind75, spring, blind75, 프로그래머스, 알고리즘, 자바, dfs, 백준, neetcode, DP, Java, programmers,

Today :
Yesterday :

kwang2134 님의 블로그