200. Number of Islands

• 전형적인 DFS  문제로, leetcode 에서 medium  로 되어 있으나, 다른 DFS 를 사용하는 문제들에 비하면 easy 인것 같다
• 풀어본적이 있고 유명한 문제여서 거의 한번에 pass는 했으나, 
• 완전히 한번에 pass 하지 못했는데, 코드를 다 짠 뒤 compile  에러가 여기저기 있었다
• [][] 배열 array 의 index 를 i, j 를 x, y 로 헷갈린다거나
• 배열 이름 오타 grid 를 gird  로 적었다거나
• 배열 index 예외 처리를  copy & paste 하느라 row, col 모두 x 에 대해 한다거나
• 예외 처리시 grid.length  보다 작아야 하는데 x == grid.length 에 대해 까먹었거나
• 하여 한번에 통과하지 못했다.
• 한번 본다고 코드를 다 짠 후 skim 하긴 했는데 위에걸 하나도 발견 못한건, 안한거나 마찬가지고 할 이유가 없는거나 마찬가지다. 정신 똑바로 차리고 꼼꼼히 봐야한다.

Time Complexity

• nested loop 로 grid 의 행과 열에 대해 한번씩 visit 하므로 O(MN),  M = grid.length, N = grid[0].length 로 보인다.

속도가 느려 (2ms) 더 빠른 사람걸 봤는데 (0ms), 나머지는 똑같은데, 전체 grid 에 대해서 for를 돌면서 dfs 를 들어가지 않고, 하나를 찾았으면, 다음 island 시작점을 찾기 위해 grid 를 따로 iterate 한다. 그게 바로 아래의 findNext 함수이다.  매우 큰 array 이에, 매우 sparse 한 경우라면, 이렇게 하는것이 더 효율적일 수 있겠다. 매번 dfs 들어가서 edge 체크하는 불필요한 작업을 하지 않으니.

public static int[] findNext(char[][] grid, boolean[][] visited, int r, int c) {
    for (int cc = c; cc<grid[r].length; cc++) {
        if (!visited[r][cc] && grid[r][cc] == '1')
            return new int[] {r, cc};
    }

    for (int rr = r+1; rr< grid.length; rr++) {
        for (int cc = 0; cc< grid[r].length; cc++) {
            if (!visited[rr][cc] && grid[rr][cc] == '1')
                return new int[] {rr, cc};
        }
    }
    return new int[] {-1,-1};
}

public static void dfs(char[][] grid, boolean[][] visited, int r, int c) {
    if (r<0 || c<0 || r>=grid.length || c>=grid[r].length || visited[r][c] || grid[r][c] == '0')
        return;
    visited[r][c] = true;
    dfs(grid, visited, r-1, c);
    dfs(grid, visited, r+1, c);
    dfs(grid, visited, r, c-1);
    dfs(grid, visited, r, c+1);
}

public int numIslands(char[][] grid) {
    boolean[][] visited = new boolean[grid.length][grid[0].length];
    int count = 0;
    int[] nextVisit = findNext(grid, visited, 0, 0);
    while (nextVisit[0] != -1 && nextVisit[1] != -1) {
        count++;
        dfs(grid, visited, nextVisit[0], nextVisit[1]);
        nextVisit = findNext(grid, visited, nextVisit[0], nextVisit[1]);
    }
    return count;
}