No1260 DFS와 BFS(그래프 이론: 너비우선탐색, 깊이우선탐색)

백준 7576 번(토마토)를 풀기 전에 먼저 전에 풀었던 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search) 기본 문제인 이 문제의 문제풀이를 기록하면서 두 가지 알고리즘을 정리해보고자 한다.

 

1. 깊이 우선 탐색(DFS)

간선들로 연결된 점들을 이차원 배열(int[][])로 표현한 후 i와 j 사이를 연결하는 간선이 있을 경우 arr[i][j], arr[j][i]의 값을 1로, 없을 경우 0으로 표현한다. 이후 탐색할 때 i와 연결된 점들을 찾을 때 arr[i]의 값들을 검색하면 된다.

한번 검색한 곳을 다시 지나치지 않기 위해 visit(boolean[]) 배열 하나를 만들어 i번째 점을 검색한 후 visit[i]는 true값으로 변경한다. 검색 조건으로는 !visit으로 준다. i의 점과 연결되어 있는 전체 점을 검색하는 For문 안에 연결되어 있는 점을 발견할 경우 그 점과 연결되어 있는 전체 점을 검색하는 메소드를 다시 호출한다. 이렇게 할 경우 검색 순서는 시작점으로부터 가장 멀리 있는, 가장 깊숙한 점까지  내려가 같은 부모를 가진 형제 노드를 다 검색한 후 다시 다음 부모의 형제 노드로 넘어간다.

 

부끄러운 내 그림 실력으로 표현해보면 아래와 같다.

dfs

코드는 아래와 같다.

static boolean[] visit;
static int[][] map;
	
public static void dfs(int i) {

	visit[i]=true;
	System.out.print(i+1+" ");
	for (int j = 0; j < map[i].length; j++) {
		if(map[i][j]==1 && !visit[j]) {
			dfs(j);
		}
	}
}

 

2. 너비 우선 탐색(bfs)

너비 우선 탐색도 마찬가지로 연결된 두 점의 간선의 유무에 따라 2차원 배열을 만들고 이미 검색했는지 알 수 있도록 visit(boolean[]) 배열을 만든다. 깊이 우선 탐색과의 가장 큰 차이점은 깊이 우선 탐색은 한 점과 연결된 다른 점을 검색하기 위해 for문을 돌 때 연결된 다른 점을 만나면 바로 다시 그점과 연결된 다른 연결된 점을 검색하도록 재귀 함수를 사용했다면, 깊이 우선 탐색은 처음 연결된 다른 점을 만났을 때 검색 했다는 표시를 한 후(visit[i]=true) 그 점과 연결된 다른 점을 검색하는 작업은 queue에 잠시 미루어둔다는 점이다. 그럴 경우, for문에서 1차적으로 연결된 점들을 다 검색하기 전까지 그 자식 노드들에 접근하지 않는다. 그렇게 첫번째 for문이 끝나면 for문을 돌면서 queue에 저장해놨던 점들의 자식노드들을 순서대로 검색하게 된다. 부끄러운 내 그림으로 표현하자면 이와 같다.

 

bfs

코드는 아래와 같다.

public static void bfs(int i) {
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(i);
		visit[i]=true;
		System.out.print(i+1+" ");
		while(!queue.isEmpty()) {
			
			int a = queue.poll();
			
			for (int j = 0; j < N; j++) {
				if(map[a][j]==1 && !visit[j]) {
					visit[j] = true;
					System.out.print(j+1+" ");
					queue.add(j);
				}
			} 	
		}		
	}