DFS 알고리즘 (2) - 예제(행렬의 영역 구하기)

 

DFS를 이용하는 문제를 예로 들자면 주로 넓이 구하는 문제/ 길찾기 문제일 것입니다.

그 중 부분적인 넓이를 구하는 문제를 풀면서 정리를 좀 해보져

 

1. 문제

다음과 같은 행렬이 있다고 하자

사진 1. 행렬 영역 구하기 문제

그리고 오른쪽에 표시한 것과 같이 3부분으로 나뉘고 각각 넓이는 6/2/8 이다.

이렇듯 행렬의 각각의 영역의 넓이를 구하는 문제를 DFS를 활용하여 풀어본다.

 

2. 문제풀이

풀이 방법은 0,0 부터 탐색한다.
1. 0,0부터 시작해서 상하좌우로 움직이며 1인 곳만 탐색
2. 0을 만나면 끝내기
(DFS인데 Stack을 이용 안한 이유는 재귀함수를 이용할 경우 재귀함수 불릴때마다 메모리에 스택으로 쌓이고 처리하기 때문에 따로 Stack 만들진 않았다.)

 

3. 자바 코드

package java_BFS_DFS_basic;
import java.util.ArrayList;
/*
 * DFS를 이용하여
 * (NxN)인접행렬 넓이 구하기
 * */
public class adjMatrics_DFS {
	 private static int[] X = {-1,0,1,0}; // X축의 상하좌우 이동을 위한 배열 
	 private static int[] Y = {0,1,0,-1}; // Y축의 상하좌우 이동을 위한 배열 (x,y 짝만 맞추어주면 상하좌우든 하좌우상 이든 순서 상관x)
	 private static int[][] map;
	 private static int cnt=1;
	 
	 
	 public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<Integer> arr = new ArrayList<Integer>(); //각 영역의 넓이를 저장할 ArrayList 생성
		adjMatrics_DFS b = new adjMatrics_DFS(); 
		int[][] map = {{1,1,1,0,1},
					   {1,1,0,0,1},
					   {1,0,1,1,0},
					   {0,0,1,1,1},
					   {0,0,1,1,1}};
		boolean[][] check = new boolean[map.length][map[0].length]; //방문한 곳을 체크하기 위한 배열 행렬 생성
		
		for(int i=0; i<map.length; i++) {
			//System.out.println("다음 찾기 시작");
			//(0,0) 부터 탐색 시작 후 1을 만나면 넓이 구하기 시작
			for(int j=0; j<map[i].length; j++) {
				if(map[i][j] == 1) {
					b.dfs(i,j,check,map);
					arr.add(cnt);
					cnt = 1;
				}
			// 아닌경우 continue
				else
					continue;
			}
		}
	//	System.out.println("프로그램 종료");
		System.out.println("arr : "+ arr);
	}
	 
	 public void dfs(int x, int y, boolean[][] ck,int[][] map) {
		 
		 System.out.println(x+","+y);
		 ck[x][y] = true;
		 map[x][y] = 0;
		 
		 for(int i=0; i<4; i++) {
			 int nextX = x + X[i];
			 int nextY = y + Y[i];
			//상,하,좌,우 이동 중 범위가 넘어서는 경우 continue
			if(nextX <0 || nextY<0 || nextX>=ck.length || nextY>=ck.length) {continue;}
			//방문한곳은 continue
			if(ck[nextX][nextY]){continue;}
			//0은 벽이라서 이동할 경로가 벽이면 continue
			if(map[nextX][nextY] == 0) {ck[nextX][nextY] = true; continue;}
			
			dfs(nextX,nextY,ck,map);
			cnt++;
		 }
		 //System.out.println("END");
		 //System.out.println();
	 }
}

 

출력 결과 :  arr : [6, 2, 8]

 

DFS / BFS 이론은 알겠는데, 문제를 풀다보면 어떻게 구현하지? 라는 생각이 많이 든다.
그래서 다음글엔 DFS / BFS를 어떻게 구현할지 정리해 본다.