LeetCode: 200번 (Number of Islands) [JAVA]

문제 링크

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 반환할 answer 값 0으로 초기화
2. bfs 기반으로 주어진 grid를 탐색, 전체 grid를 돌며 해당 위치가 '1'인 경우 큐에 해당 위치를 넣고 bfs를 진행하여 현재 '1'과 연결된 위치의 값들을 모두 찾아 '0'으로 초기화한다. 이후 answer = answer +1
3. 해당 answer 값 반환

 기본적인 bfs 탐색을 통해 해결할 수 있는 문제이다. 문제에서는 주어진 grid 속 섬들의 개수를 반환하면 되는 것으로, 하나의 섬은 상하좌우가 '1'들로 연결된 지역인 것이다. 그렇기 때문에 하나의 '1'을 찾게 되면 동시에 연결된 주변 '1'들을 모두 찾아 방문 표시를 해서 중복을 방지한다. 이런 경우 대부분 visited 배열을 활용하지만, 이번 문제에서는 기존 주어진 grid 배열을 활용하여 단순 '0'으로 표시하면 기존 visited 배열의 역할을 대체할 수 있다.

 그렇기 때문에 이중 for문을 통해 전체 grid를 돌며, 만약 현재 위치의 값이 '1'인 경우 해당 좌표를 큐에 넣고 bfs 탐색을 진행한다. 이를 통해 지금 위치의 '1'과 상하좌우로 연결된 '1'들을 모두 찾아 '0'으로 초기화하고, 해당 탐색이 끝나면 answer의 값을 +1 한다. 이후 전체 반복문 탐색이 끝나고 해당 answer 값을 반환하면 된다.

 

class Solution {
    Queue<Point> q = new LinkedList<>();

    public int numIslands(char[][] grid) {
        int answer = 0, r = grid.length, c = grid[0].length;

        for (int i = 0; i < r; i++) {//전체 grid를 돌며
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == '1') {//지상인 경우(+ 방문하지 않은 경우)
                    q.add(new Point(i, j));

                    while (!q.isEmpty()) {//bfs 탐색
                        Point now = q.poll();

                        if (now.r < 0 || now.r >= r || now.c < 0 || now.c >= c
                                 || grid[now.r][now.c] == '0') {//예외 사항
                            continue;
                        }

                        grid[now.r][now.c] = '0';//방문 표시

                        q.add(new Point(now.r + 1, now.c));
                        q.add(new Point(now.r - 1, now.c));
                        q.add(new Point(now.r, now.c + 1));
                        q.add(new Point(now.r, now.c - 1));
                    }

                    ++answer;
                }
            }
        }

        return answer;
    }

    class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

결과