DFS 예제 코드

 

 

public class DFS_EX {
	static int row, col;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);

		col = input.nextInt();
		row = input.nextInt();

		map = new int[row][col];
		visit = new boolean[row][col];

		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				map[i][j] = input.nextInt();
			}
		}

		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				if(map[i][j] == 1) {
					visit[i][j] = true;
					dfs(i, j, 0);
				}
			}
		}
	}

	private static void dfs(int x, int y, int depth) {
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(nx >= 0 && ny >= 0 && nx < row && ny < col) {
				if(!visit[nx][ny] && map[nx][ny] > depth) {
					visit[nx][ny] = true;
					map[nx][ny] = depth + 1;
					dfs(nx, ny, depth + 1);
					visit[nx][ny] = false;
				}
			}
		}
	}
}

 

위의 코드를 보게되면 맵에 대한 2차원 배열과 방문여부에 대한 2차원 배열을 생성하여 값을 입력받는다.

BFS와 다른점은 재귀를 통해서 결과를 도출한다는 점이다.

 

첫 시작점부터 시작해서 방문을 이어가는데 여기서 dfs function 내부를 살펴보게되면 bfs와 마찬가지로 dx, dy 배열을 이용해서 상하좌우를 탐색하게 되고, 이 상하좌우를 탐색하는 값이 map 전체의 크기를 벗어나지 않도록 조건을 준다. 그 다음 if문에서는 visit의 값이 존재하지 않고 map의 해당 배열이 depth보다 작은 경우에만 탐색하게된다(depth에 대해서 먼저 탐색하기 때문). 이러한 탐색을 하기 때문에 stack과 같은 구조로 계속 쌓이고 조건에 만족하는 것이 없으면 출력하는 선입후출(LIFO)형태를 띄며 탐색하게된다.