[Java] leetcode 200. Number of Islands

문제

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

Number of Islands - LeetCode

주어진 2차원 배열에서 '1' 부분의 집합들의 개수를 리턴하는 문제

알아야 할 개념

• 큐를 사용한 2차원 배열 탐색(DFS)

 

풀이

풀이는 다음과 같다.

1. 2중 for문으로 배열을 모두 탐색한다.
2. island 부분 '1' 을 만나면 DFS 탐색한다. 
3. DFS 탐색을 끝나면 탐색한 부분을 '2' 로 마킹해준다. 
4. 답을 리턴한다. 

 

 

큐를 사용하여 DFS 를 하였다. DFS 구현에는 재귀 함수 방법과 Queue, for문을 사용하는 두 가지 방법이 있는데 , 재귀 함수보다 queue for 문이 속도가 좀 더 빠르다.

 

2중 for문으로 배열을 탐색하다가 island 부분인 '1' 을 만나면 그때부터 right, left, up, down 4방향 탐색을 진행한다. 

//down, right, up, left
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

다음과 같이 direction X , direction Y 배열들을  좌표 (x,y) 에 더할 원소들로 초기화 해준다. 그러면 for문을 이용하여 왼오위아래 4방향 탐색이 가능하다. 

			for(int k = 0 ;k < 4 ;k++){
                            int nx = c[0]+dx[k];
                            int ny = c[1]+dy[k];
                            if(nx < 0 || ny < 0 || nx >m-1 || ny  > n-1 || grid[nx][ny] != '1')continue;
                            Q.offer(new int[]{nx,ny});
                            grid[nx][ny] = '2';
                        }

next X, next Y 를 만들어서 4방향 탐색을 하는 코드이다. 만약 nx,ny 부분이 '1' 이 아니라면 스킵. '1'인 좌표는 다시 큐에 집어넣고 마킹을 한다. 

 

여기서 주의할 점은 큐에 좌표를 추가할때 방문 처리를 해야한다.
큐에 꺼낼때 체크하면 메모리 오버플로우가 발생한다.

코드

자바

class Solution {
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    public int numIslands(char[][] grid) {
        int ans = 0;
        int m = grid.length; 
        int n = grid[0].length;
        Queue<int[]> Q= new LinkedList<>();
        for(int i =0 ;i< m ;i++){
            for(int j =0 ; j< n ;j++){
                if(grid[i][j] == '1'){
                    ans++;
                    Q.offer(new int[]{i,j});
                    grid[i][j] = '2';
                    while(!Q.isEmpty()){
                        int c[] = Q.poll();
                        for(int k = 0 ;k < 4 ;k++){
                            int nx = c[0]+dx[k];
                            int ny = c[1]+dy[k];
                            if(nx < 0 || ny < 0 || nx >m-1 || ny  > n-1 || grid[nx][ny] != '1')continue;
                            Q.offer(new int[]{nx,ny});
                            grid[nx][ny] = '2';
                        }
                    }
                }
            }
        }
        return ans;
    }
}