200. Number of Islands

문제

전형적인 bfs 탐색 문제였다. 0은 물, 1은 땅을 의미하는 그래프 배열이 주어진다. 땅이 근접하게 모여 있으면 하나의 섬이다. 섬의 갯수를 요구하는 문제였다.

링크: https://leetcode.com/problems/number-of-islands/description/

Solution

class Solution {
    static int[][] dirArray = {{-1,0},{1,0},{0,-1},{0,1}};
    public int numIslands(char[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        boolean[][]visited = new boolean[m][n];
        int answer=0;

        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(!visited[i][j] && grid[i][j]=='1') {
                    answer++;
                    bfs(grid, visited, new int[]{i,j});
                }

            }
        return answer;
    }

    public void bfs(char[][] grid, boolean[][] visited, int[] start) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> q =new LinkedList<>();
        q.offer(start);
        visited[start[0]][start[1]] = true;

        while(!q.isEmpty()) {
            int[] cur = q.poll();

            for(int[] d: dirArray) {
                int[] next = new int[]{cur[0]+d[0], cur[1]+d[1]};
                if(next[0]>=0 && next[0]<m && next[1]>=0 && next[1]<n &&
                visited[next[0]][next[1]]==false && grid[next[0]][next[1]]=='1') {
                    q.offer(next);
                    visited[next[0]][next[1]] = true;
                } 
            }
        }
    }
}

회고

                if(!visited[i][j] && grid[i][j]=='1') {
                    answer++;
                    bfs(grid, visited, new int[]{i,j});
                }

if문의 중괄호를 빼먹어서 틀린 이유를 한참을 찾았다...주의...하자...