[자료구조]DFS(깊이 탐색 알고리즘)

1. 정의

- 그래프 탐색의 한 종류로 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것

- 자세하게는 루트노드( 혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 넓게(Wide) 탐색하기 전에 깊게(deep) 탐색하는 방식의 알고리즘

2. 특징

-  자기 자신을 호출하는 순환 알고리즘(재귀)의 형태를 가짐

- 전위 순회(Pre-Order Trversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

-  DFS 알고리즘 사용시 어떤 노드를 방문했었는지를 반드시 확인하여야함(안그러면 무한루프가 발생할 수 있음)

 

 

3. DFS 동작 과정

 

1.  0번 노드가 시작 정점이라고 한다면 0번 노드와 인접한 노드들을 차례로 순회한다. 만약 인접한 노드가 없다면 종료한다.
2.  0번 노드와 인접한 1번 노드를 방문하고, 다시 1번 노드와 인접한 노드 0번과 2번 중 0번은 방문했기 때문에 2번 노드를 방문한다.
3. 다시 2번 노드에서 인접한 노드를 검색하고 방문했는지를 확인한다. 2번 노드와 인접한 3번 노드를 방문한다.
4. 3번 노드에서 4번 노드로 방문한다. 4번 노드 입장에서는 0번과 2번 노드가 이미 방문한것으로 나오기 때문에 전 노드인 3번으로 돌아가 방문하지 않은 노드가 있는지 확인한다. 동일하게 backtracking을 하여 방문하지 않은 노드가 있는지 확인한다.

4. 사용예시

- 미로를 탐색할 때 한 방향으로 갈 수 있을때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색하는 경우

5. 구현방법

- 1. 순환호출(재귀)

package Graph;
/*
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
	Example 1:
	Input:
	11110
	11010
	11000
	00000
	Output: 1
	Example 2:
	Input:
	11000
	11000
	00100
	00011
	Output: 3
	
	DFS:깊이 우선탐색
*/
public class NumberOfIsland_dfs {
	public static void main(String[] args) {
		char[][] grid= {
						{'1','1','1','0','0'},
						{'1','1','0','0','0'},
						{'0','0','1','0','1'},
						{'0','0','0','1','1'}
					   };
		
		NumberOfIsland_dfs a = new NumberOfIsland_dfs();
		System.out.println(a.numsIslands(grid));
	}

	//1. 1이 있으면 동서남북에 1이 또 있는지 확인
	//2. 확인 후 해당 1을 왔다갔다고 표시함
	private int numsIslands(char[][] grid) {
		int count=0;
		if(grid==null || grid.length==0) return 0;
		for(int i=0;i<grid.length;i++) {
			for(int j=0;j<grid[i].length;j++) {
				if(grid[i][j]=='1') {
					count++;
					checkVisited(grid,i,j);
					System.out.println("변경");
				}
			}
		}
		
		return count;
	}

	private void checkVisited(char[][] grid, int i, int j) {
		int xSize = grid.length;
		int ySize = grid[0].length;
		//만약 grid의 사이즈를 벗어나거나 1이 아니라면 종료
		if(i<0 || j<0 || i>=xSize || j>=ySize || grid[i][j]!='1') return;
		//방문한 지점은 X로 변경
		grid[i][j]='X';
		
		//동서남북으로 재귀함수 호출
		checkVisited(grid,i-1,j);
		checkVisited(grid,i+1,j);
		checkVisited(grid,i,j-1);
		checkVisited(grid,i,j+1);
		print(grid);
	}
	//출력함수
	public void print(char[][] grid) {
		for(int i=0;i<grid.length;i++) {
			for(int j=0;j<grid[i].length;j++) {
				System.out.print(grid[i][j]+" ");
			}
			System.out.println();
		}
	}
}