[자바 알고리즘 인터뷰] 12장 그래프 (1) 섬의 개수

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

 

 

- 1을 육지로, 0을 물로 가정한 2차원 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라

(연결되어 있는 1의 덩어리 개수를 구하라)

 

 

풀이 1) DFS로 그래프 탐색 

 

- 입력값이 정확히 그래프는 아니지만 사실상 동서남북이 모두 연결된 그래프로 가정하고 동일한 형태로 처리할 수 있으며, DFS 재귀를 이용해 네 방향 각각의 탐색을 끝마치면 1이 증가하는 형태로 육지의 개수를 파악할 수 있다. 

 

- 먼저 여기서는 행렬 입력값인 grid의 행, 열 단위로 육지(1)인 곳을 찾아 진행하다가 육지를 발견하면 그때부터 dfs()를 호출해 탐색을 시작한다. 

 //행렬을 모두 탐색
 for(int i=0; i<grid.length; i++)
 {
     for(int j=0; j<grid[i].length; j++)
     {
         //만약 육지(1)인 경우 dfs 시작
         if(grid[i][j] == '1')
         {
             dfs(i,j,grid);
            ...

 

 

- dfs 함수는 동서남북을 모두 탐색하면서 재귀 호출하는 구조로 되어있다. 

- 함수 가장 상단에는 육지가 아닌 곳은 return으로 종료 조건으로 설정해서 재귀 호출이 백트래킹으로 모두 빠져나오면 섬 하나를 발견한 것으로 간주한다. 

- 이때 이미 방문했던 곳은 1이 아닌 값으로 마킹한다. (육지(1)를 더 이상 아닌 것으로 만들면 됨, 방문 배열 안써도 됨, 일종의 가지치기)

 

public void dfs(int i, int j, char grid[][])
    {
        //현재 위치가 그리드 밖이거나, 물(0)인 경우 종료
        if(i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j] =='0')
            return;
        //한 번만 탐색하기 위해 탐색한 지점은 물(0)로 변경
        grid[i][j] = '0';

        //동서남북 재귀 DFS
        dfs(i,j+1,grid); //동
        dfs(i,j-1,grid); //서
        dfs(i+1,j,grid); //남
        dfs(i-1,j,grid); //북 
    }

 

 

- dfs() 함수를 빠져나온 후에는 해당 위치에서 탐색할 수 있는 모든 육지를 탐색한 것이므로, 카운트를 1 증가시킨다. 

- 이런식으로 grid 행렬을 모두 탐색하면 결과를 구할 수 있다. 

 

 dfs(i,j,grid);
 //재귀 dfs가 모두 끝나면 섬 하나가 완성됐으므로 +1
 count++;

 

 

 

class Solution {
    public void dfs(int i, int j, char grid[][])
    {
        //현재 위치가 그리드 밖이거나, 물(0)인 경우 종료
        if(i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j] =='0')
            return;
        //한 번만 탐색하기 위해 탐색한 지점은 물(0)로 변경
        grid[i][j] = '0';

        //동서남북 재귀 DFS
        dfs(i,j+1,grid); //동
        dfs(i,j-1,grid); //서
        dfs(i+1,j,grid); //남
        dfs(i-1,j,grid); //북 
    }
    public int numIslands(char[][] grid) {
        int count = 0;

        //행렬을 모두 탐색
        for(int i=0; i<grid.length; i++)
        {
            for(int j=0; j<grid[i].length; j++)
            {
                //만약 육지(1)인 경우 dfs 시작
                if(grid[i][j] == '1')
                {
                    dfs(i,j,grid);
                    //재귀 dfs가 모두 끝나면 섬 하나가 완성됐으므로 +1
                    count++;
                }
            }
        }

        //섬의 개수 리턴
        return count;
    }
}

3밀리초