Questions : Number of Islands

1. 배열 안에 섬이 몇 개인지를 찾는 문제이다.

 

200. Number of Islands

 

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [

    ["1","1","1","1","0"],

    ["1","1","0","1","0"],

    ["1","1","0","0","0"],

    ["0","0","0","0","0"] ]

 

Output: 1

 

Example 2:

Input: grid = [

    ["1","1","0","0","0"],

    ["1","1","0","0","0"],

    ["0","0","1","0","0"],

    ["0","0","0","1","1"] ]

 

Output: 3

 

3. 방법은

  3-1 0,0 셀부터 시작하여 1인 것을 발견하면 bfs을 실행하여 연결된 그래프를 찾으면서 모두 0으로 바꾼다.

  3-2 그러면 연결되지 않은 부부만 남게 된다. 2-1에서 bfs를 시작한 바로 다음 위치부터 계속 해 나간다.

    3-2-1 3-1 때문에 이미 연결된 것은 0으로 바뀌었을 것이므로 1이 발견되면 다른 섬의 일부인 것이다.

 

 

import java.util.LinkedList;
import java.util.Queue;

public class App2 {
  
  public static void main(String[] args) {
    Solution1 sol = new Solution1();
    // char[][] grid = {
    //   {'1','1','1','1','0'},
    //   {'1','1','0','1','0'},
    //   {'1','1','0','0','0'},
    //   {'0','0','0','0','0'}};

      char[][] grid = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
      };

    System.out.println(sol.numIslands(grid));
  }
}

class Solution1 {   
  class Point {
    public int row, col;

    public Point(int row, int col) {
      this.row = row;
      this.col = col;
    }

    public String toString() {
      return "[ " + row + " , " +  col + " ]";
    }
  }

  public int numIslands(char[][] grid) {    

    int numOfIslands = 0;

    for (int i=0; i<grid.length; i++) {
      for (int j=0; j<grid[0].length; j++) {
        if (grid[i][j] == '1') {
          System.out.println("\nStaring point [ " +  i + ", " + j + " ]");
          bfs(grid, new Point(i, j));
          numOfIslands++;
        }
      }
    }
    return numOfIslands;
  }

  private void bfs(char[][] grid, Point point) {
    Queue<Point> queue = new LinkedList<>();
    int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    queue.add(point);

    while (!queue.isEmpty()) {
      int size = queue.size();
      System.out.println(queue.toString());
      
      for (int i=0; i<size; i++) {
        Point position = queue.poll();
        grid[position.row][position.col] = '0';

        for (int[] direction : directions) {
          int newRow = position.row + direction[0];
          int newCol = position.col + direction[1];

          if (newRow >= 0 && newRow < grid.length && 
              newCol >= 0 && newCol < grid[0].length && 
              grid[newRow][newCol] == '1') {
            queue.add(new Point(newRow, newCol));
          }
        }
      }
    }
  }
}

 

4. 결과 화면