leetcode: Number of Islands

전형적인 bfs문제이다. 

시간복잡도는 O(grid 요소의 갯수)와 같다.

import java.util.*;
class Solution {
	public static int dr[] = { 0, 1, 0, -1 };
	public static int dc[] = { 1, 0, -1, 0 };

	public int numIslands(char[][] grid) {
		int answer = 0;

		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				if (grid[i][j] == '1') {
					answer++;
					grid[i][j] = '0';
					bfs(i, j, grid);
				}
			}
		}
		return answer;
	}

	public static void bfs(int row, int col, char[][] grid) {
		Queue<Position> queue = new LinkedList<Position>();
		queue.add(new Position(row, col));

		while (!queue.isEmpty()) {
			Position now = queue.poll();

			for (int i = 0; i < 4; i++) {
				int newRow = now.row + dr[i];
				int newCol = now.col + dc[i];

				if (isBoundary(newRow, newCol, grid) && grid[newRow][newCol] == '1') {
					grid[newRow][newCol] = '0';
                    queue.add(new Position(newRow, newCol));
				}
			}
		}
	}

	public static boolean isBoundary(int row, int col, char[][] grid) {
		if (row < 0) {
			return false;
		}
		if (row >= grid.length) {
			return false;
		}
		if (col < 0) {
			return false;
		}
		if (col >= grid[row].length) {
			return false;
		}

		return true;
	}
}

class Position {
	int row, col;

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