MaxOfIsland(가장큰섬 구하기) : DFS문제

어제에 이어서 DFS 알고리즘 문제를 풀어보았다. MaxOfIsland라는 문제인데 어제와 비슷한 문제이지만 더 심화된 내용이다.

문제의 내용은 이러하다. 숫자 배열이 주어지고 1은 육지, 0은 바다라고 생각했을때 바다로 둘러싸인 섬들이 존재하는데 그 중에 섬의 크기가 가장큰 즉,1의 개수가 가장많은 섬의 1의 개수를 출력하는 문제이다.

어제와 같이 DFS(깊이우선탐색) 방식을 사용하였다.

package alogrithm_test;
import java.util.*;
public class MaxOfIsland {
		public static void main(String[] args) {
			int[][] island = {{1,1,0,1,1},
					          {0,1,1,0,0},
					          {0,0,0,0,0},
					          {1,1,0,1,1},
					          {1,0,1,1,1},
					          {1,0,1,1,1}};
			MaxOfIsland a= new MaxOfIsland();
			System.out.println(a.max(island));
			
			
		}
        //방향을 나타내는 배열생성
		int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
        
		int m,n;
		public  int max(int[][] grid) {
        	//오류처리
			if(grid == null || grid.length ==0) 			return 0;
            
			m= grid.length;
			n=grid[0].length;
			int max2=0;
			for(int i=0;i<m;i++) {
				for(int j=0;j<n;j++) {
                	//배열의 값이 1이면
					if(grid[i][j]==1) {
						
						//area변수에 1의 개수 저장
						int area=dfs(grid,i,j,0);
                        
                        //가장큰 area의 크기를 구한다.
						max2= Math.max(max2,area);
					}
				}
			}
			return max2;
			
		}
		 int dfs(int[][] grid,int i,int j,int area) {
			
            //dfs를 빠져나가기 위한 문장
			if(i<0 || i>=m || j<0 ||j>=n|| grid[i][j] ==0) return area;
            
            	//값이 1인 배열의 데이터는 방문체크를 위해 0으로 바꿔준다.
			     grid[i][j]=0;
                 
                 //area값을 1 증가시킨다.
			     area++;
                 
				for(int[] dirs : dir) {
                	//기준으로부터 상하좌우 탐색을 실시한다.
					area=dfs(grid, i+dirs[0] , j + dirs[1] ,area);
				}
			return area;
		}
		
			}

출력값 : 8

이러한 코드를 통해 가장큰섬의 크기를 구할 수 있었다.
DFS관련 문제는 stack 또는 재귀문장을 통해서 해결할 수 있는데 재귀문장을 선호하는 편이다.

이제 내일이면 sw마에스트로 코딩테스트를 보게 되는데 아직 부족한 부분이 많은 실력이라서 걱정이된다.

알고리즘 문제 해결 능력이라는게 단시간에 생기는 게 아닌거 같아서 이번에 좋은 결과가 없더라도 꾸준히 진행하면서 차근차근 실력을 키워갈 예정이다.