LeetCode - Numbers of Island

문제

💡 주어진 이차원 배열에서 문자 1은 땅을 0은 물을 의미한다. 모든 섬의 갯수를 구하시오.

예시

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

제약 조건

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 는 '0' 또는 '1' 이다.

문제 링크 -> https://leetcode.com/problems/number-of-islands/

풀이

문제 이해하기

• n * m은 시간복잡도를 결정하는 O(N)이다.
• n m 의 최대 크기는 300 300이다.
• 300 * 300은 10^4보다 크다. 따라서 O(N^2)보다 작은 시간복잡도의 알고리즘을 선택해야한다.
• 대각선으로 연결된 땅은 떨어져 있는 것으로 판단한다.

접근 방법 생각하기

1. 그리드를 순회하면서 땅을 찾는다.
2. 땅을 찾았다면 동서남북으로 이어진 땅이 존재하는지 확인한다.
3. 이어진 땅이 없다면 다음으로 방문하지 않은 땅을 그리드에서 찾는다.

코드 설계

1. 주어진 그리드 이차원 배열을 순회한다.
2. 배열의 요소가 문자 1 이고 방문한적이 없다면 섬 갯수를 추가한다.
3. 현재 방문 중인 땅에 이어진 땅이 있는지 BFS로 탐색한다.
4. 이어진 땅이 있다면 방문한 것으로 판정한다.

코드 구현

public class NumbersOfIsland {

    private char[][] grid;
    private boolean[][] visited;

    private int getRows() {
        return grid.length;
    }

    private int getColumns() {
        return grid[0].length;
    }

    public int solve(char[][] grid) {
        this.grid = grid;
        this.visited = new boolean[getRows()][getColumns()];
        int result = 0;

        for (int i = 0; i < getRows(); i++) {
            for (int j = 0; j < getColumns(); j++) {
                if (isIsland(i, j) && isNotVisited(i, j)) {
                    result++;
                    bfs(i, j);
                }
            }
        }
        return result;
    }

    private void bfs(int curRow, int curColumn) {
        Queue<Coordinate> queue = new ArrayDeque<>();
        visited[curRow][curColumn] = true;
        queue.add(new Coordinate(curRow, curColumn));

        while (!queue.isEmpty()) {
            Coordinate coordinate = queue.poll();
            queue.addAll(getNeighbors(coordinate));
        }
    }

    private List<Coordinate> getNeighbors(Coordinate curCoordinate) {
        List<Coordinate> result = new ArrayList<>();

        for (Directions direction : Directions.values()) {
            int newRow = curCoordinate.getRow() + direction.getDirection().getRow();
            int newColumn = curCoordinate.getColumn() + direction.getDirection().getColumn();

            if (validCoordinate(newRow, newColumn)) {
                result.add(new Coordinate(newRow, newColumn));
                visited[newRow][newColumn] = true;
            }
        }

        return result;
    }

    private boolean validCoordinate(int row, int column) {
        return isInBoundary(row, column) && isIsland(row, column) && isNotVisited(row, column);
    }

    private boolean isInBoundary(int row, int column) {
        return row >= 0 && column >= 0 && row < getRows() && column < getColumns();
    }

    private boolean isIsland(int curRow, int curColumn) {
        return grid[curRow][curColumn] == '1';
    }

    private boolean isNotVisited(int curRow, int curColumn) {
        return !this.visited[curRow][curColumn];
    }
}

public class Coordinate {

    private final int row;
    private final int column;

    public Coordinate(int row, int column) {
        this.row = row;
        this.column = column;
    }

    public int getRow() {
        return row;
    }

    public int getColumn() {
        return column;
    }
}

public enum Directions {

    NORTH(new Coordinate(0, 1)),
    EAST(new Coordinate(1, 0)),
    SOUTH(new Coordinate(0, -1)),
    WEST(new Coordinate(-1, 0));

    private final Coordinate direction;

    Directions(Coordinate direction) {
        this.direction = direction;
    }

    public Coordinate getDirection() {
        return direction;
    }
}

테스트 코드

class NumbersOfIslandTest {

    @Test
    void testNumbersOfIsland() {
        //given
        char[][] grid1 = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };

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

        NumbersOfIsland numbersOfIsland = new NumbersOfIsland();

        //when
        int result1 = numbersOfIsland.solve(grid1);
        int result2 = numbersOfIsland.solve(grid2);

        //then
        Assertions.assertEquals(1, result1);
        Assertions.assertEquals(3, result2);
    }

}