[java] Number of Islands

[참고문제] : https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

문제 풀이

DFS/BFS 문제이고, 연결된 구간의 갯수를 찾는 문제다.

특히나, 전형적인 문제라 BFS로 풀어보기로 했다.

 

생각의 흐름 -  방문 여부는 누적되도 된다.

이전에 풀었던 문제는 중복적으로 체크하면 안되었기 때문에, 다시 돌려주는 방법을 사용했지만 이번에는 중복해서 활용해야만 한다.

 

생각의 흐름 - Count에 대한 분리를 잘하자.

외딴 섬이 몇개인지 알아봐야 하므로, Count 측정 지점을 잘 체크해야 한다.

즉, 새로운 '1'이 나오면 count를 올리고, 인접한 상,하,좌,우에 '1'인 지점을 bfs로 모두 방문했다고 체크해야 한다.

그래야 외딴 섬의 갯수가 정확하게 나온다.

 

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        boolean[][] isVisited = new boolean[m][n];

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(!isVisited[i][j] && grid[i][j] == '1') {
                    count ++;
                    // BFS
                    Queue<Node> que = new LinkedList<>();
                    que.add(new Node(i,j));
                    while(!que.isEmpty()) {
                        Node tmp = que.poll();
                        if(isVisited[tmp.row][tmp.col] || grid[tmp.row][tmp.col] != '1')
                            continue;
                        isVisited[tmp.row][tmp.col] = true;
                        if(tmp.row != 0) {
                            que.add(new Node(tmp.row-1, tmp.col));
                        }
                        if(tmp.row != m-1) {
                            que.add(new Node(tmp.row+1, tmp.col));
                        }
                        if(tmp.col != 0) {
                            que.add(new Node(tmp.row, tmp.col-1));
                        }
                        if(tmp.col != n-1) {
                            que.add(new Node(tmp.row, tmp.col+1));
                        }
                    }
                }
            }
        }

        return count;
    }
    class Node {
        int row;
        int col;
        Node(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}