(Graph, Medium) Number of Islands

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

여기저기서 많이 본 것 같은 섬 찾기 문제다.

보면 떠오르는 아이디어는
0, 0부터 시작해서 m, n 까지 순회하며 "1"로 시작하는 경우 뻗어나간 부분을 모두 체크
이 때 중복 제거하기 위해 섬을 다시 물로 바꿔도 될 것 같고, 아니면 visited 배열을 따로 만들어 체크해도 될 듯

처음 풀이 - 시간 초과

처음에 아래처럼 풀었는데 시간 초과함.
한 세월 지나면 답이야 나오겠지만 최적화 포인트가 어딘지 찾아야 했음.

import java.util.*;
class Solution {
    // 상하좌우
    private int[] dx = { -1, 1, 0, 0 };
    private int[] dy = { 0, 0, -1, 1 };

    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') {
                    markIsland(i, j, grid);
                    answer++;
                }
            }
        }

        return answer;
    }

    public void markIsland(int x, int y, char[][] grid) {

        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] { x, y });

        while (!que.isEmpty()) {
            int[] current = que.poll();
            int currX = current[0];
            int currY = current[1];

            grid[currX][currY] = '0';

            for (int i=0; i<4; i++) {
                int nextX = currX + dx[i];
                int nextY = currY + dy[i];

                if (nextX >= grid.length || nextX < 0) {
                    continue;
                }
                if (nextY >= grid[0].length || nextY < 0) {
                    continue;
                }
                if (grid[nextX][nextY] == '0') {
                    continue;
                }
                que.offer(new int[] { nextX, nextY });
            }
        }
    }
}

최적화

큐에 넣을 때 방문 처리 vs 큐에서 뺄 때 방문처리
무조건 넣을 때 처리하는게 좋음. 큐에 중복을 넣어놓고서 뺄 때 체크하면 그만큼 자원 낭비임

큐에 넣을 때 방문처리하는 것으로 변경했고, 결과적으로 시간 초과 나지 않음

import java.util.*;
class Solution {
    // 상하좌우
    private int[] dx = { -1, 1, 0, 0 };
    private int[] dy = { 0, 0, -1, 1 };

    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') {
                    markIsland(i, j, grid);
                    answer++;
                }
            }
        }

        return answer;
    }

    public void markIsland(int x, int y, char[][] grid) {

        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] { x, y });
        grid[x][y] = '0';

        while (!que.isEmpty()) {
            int[] current = que.poll();
            int currX = current[0];
            int currY = current[1];

            for (int i=0; i<4; i++) {
                int nextX = currX + dx[i];
                int nextY = currY + dy[i];

                if (nextX >= grid.length || nextX < 0) {
                    continue;
                }
                if (nextY >= grid[0].length || nextY < 0) {
                    continue;
                }
                if (grid[nextX][nextY] == '0') {
                    continue;
                }
                que.offer(new int[] { nextX, nextY });
                grid[nextX][nextY] = '0';
            }
        }
    }
}