Forest Gump?

[LeetCode] Number of Islands - with DFS 본문

카테고리 없음

[LeetCode] Number of Islands - with DFS

code1010 2024. 3. 17. 19:00

문제 조건

'1'(땅)과 '0'(물)의 지도를 나타내는 m x n 2D 이진 그리드 그리드가 주어지면 섬의 수를 반환합니다. 섬은 물로 둘러싸여 있으며 인접한 육지가 수평 또는 수직으로 연결되어 형성됩니다. 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다.

입출력

INPUT : 

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


OUTPUT : 2

문제 접근

DFS를 이용하여 네 방향 각각의 탐색을 끝맞치면 1이 증가하는 형태로 육지의 개수를 파악하는 방법으로 한다.
단 이미 진행한 행렬의 값의 경우 값을 마킹을 하여 중복 순회가 안되도록 한다.

문제 풀이

public static void main(String[] args) {

      var grid = new char[][]{
              {'1', '1', '0', '1', '0'},
              {'1', '1', '0', '0', '0'},
              {'1', '1', '1', '1', '0'},
              {'0', '0', '0', '0', '0'}
      };

      noi(grid);
  }

  public static int noi(char[][] grid) {


      int count = 0;
      for (int i = 0; i < grid.length; i++){
          for(int j = 0; j < grid[i].length; j++){

              if(grid[i][j] == '1'){
                  dfs(i,j,grid);
                  count++;
              }
          }
      }
    return count;
  }

    public static void dfs(int i,int j,char[][] grid) {

      //호출하는 함수가 물밖이거나 물이면 종료
      if( i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j] == '0'){
          return;
        }
      //방문한 노드는 0으로 변경
      grid[i][j] = '0';
      dfs(i+1,j,grid);
      dfs(i-1,j,grid);
      dfs(i,j+1,grid);
      dfs(i,j-1,grid);

    }

어려웠던 점

DFS / BFS 류의 문제를 오랜만에 다시 풀어봤는데, 상황을 머리속에 그리지 않고 풀려고 하니까 많이 힘들었다.
유튜브를 참고하면서 물과 땅의 지도를 형상화 해서, 지뢰 찾기 처럼 한번 순회 시 땅을 변환하는 식으로 생각했더니
조금 형상화가 잘되서 도움이 되었다. BFS방법으로도 해당 문제를 풀어봐야겠다.

참고 자료