[그래프/개념] DFS(깊이우선탐색)과 BFS(너비우선탐색)

깊이 우선 탐색 (Depth First Search)

- 방문한 적이 없는 정점 중, 갈 수 있는 곳부터 먼저 찾아가는 탐색 방법입니다. 한 우물만 판다고 생각하면 됩니다.

- 스택구조를 사용하여 구현합니다.

- 도착 지점이 깊은 단계에 있는 경우 효율적입니다.

- 방문 순서를 활용한 자료구조 및 응용이 가능합니다. (위상정렬 등)

- 얻어진 결과가 최단거리라는 보장을 하기 힘듭니다.

- 해가 없는 경로에 빠질 가능성이 높습니다.

너비 우선 탐색 (Breadth First Search)

- 방문할 수 있는 노드들을 큐에 넣고 큐에서 pop하는 순서대로 탐색합니다.

- 큐로 구현합니다.

- 초기 정점으로부터 거리순으로 정점들을 방문합니다.

- 해를 찾게 되면 반드시 최단경로임이 보장됩니다.

그럼, 문제를 풀어보면서 이해해봅시다.

정점의 개수, 간선의 개수, 시작 정점의 번호가 주어졌을 때

DFS, BFS결과 중 오름차순 순으로 가장 빠른것을 출력해봅시다.

DFS 구현 설명

1) 그래프를 구성하기위해 인접리스트를 만들어 값을 넣습니다.

  무방향 그래프라면 양쪽 방향으로 둘 다 값을 추가해주어야 합니다.

  저는 addEdge() 라는 함수를 따로 만들어 값을 추가해주었습니다.

//간선 추가 함수
static void addEdge(int x, int y) {
	adj[x].add(y);
	adj[y].add(x);	
}	

2) 모든 리스트에 인접한 정점 번호를 정렬해줍니다.

//모든 인접리스트 값 정렬
for(int i=1; i<=V; i++){
       Collections.sort(adj[i]);
}

3) 이미 방문한 정점은 방문하지 않습니다. visited 배열을 만들고, false로 초기화해줍니다.

  //방문 배열 초기화 
  visited = new boolean[V+1];
  for(int i=1; i<=V; i++){
      visited[i] = false;
  }

4) 각 정점을 방문할 때마다 인접한 정점들 중 아직 방문하지 않은 것을 순차적으로 DFS시도해줍니다.

	private static void dfs(int curr) {
		System.out.print(curr+" ");
		visited[curr] = true;
		for(int next : adj[curr]){
			if(!visited[next]){
				dfs(next);
			}
		}		
}

BFS 구현 설명

앞에서 설명한 DFS의 1), 2), 3) 까지의 절차는 같습니다.

4) 각 정점을 방문할 때마다 인접한 정점들 중 아직 방문하지 않은 것을 순차적으로 BFS시도해줍니다.

  - Queue를 만들어서 시작정점의 번호를 add해줍니다.

  - add한 정점 방문 체크(true) 해줍니다.

  - Queue가 비어있을 때까지 방문을 시도해줍니다.

  - 큐의 사이즈를 보고 큐의 사이즈만큼 반복문을 수행해줍니다.

  - K번째 단계가 끝났을 때의 큐 크기는 K번째 단계에서 새로 방문하기 위해 큐에 넣은 K+1번째 단계에 방문할 노드의 개수가 됩니다.

     매 단계마다 처음에 있던 만큼의 정점만 방문합니다.

  - Queue에서 하나를 꺼냅니다. 꺼낸 정점의 인접한 노드들 중 아직 방문하지 않은 노드들을 다시 Queue에 넣어주고 방문체크 해줍니다.

  - 이런 식으로 먼저 방문한 노드들부터 차례대로 방문해나갑니다.

	private static void bfs(int curr) {
		Queue<Integer> que = new LinkedList<>();
		//첫 번째 값 넣기
		que.add(curr);
		visited[curr] = true;
		while(!que.isEmpty()){
			int qsize = que.size();
			for(int i=1; i<=qsize; i++){
				curr = que.poll();
				System.out.print(curr+" ");
				for(int next : adj[curr]){
					if(!visited[next]){
						visited[next] = true;
						que.add(next);
					}
				}
			}
		}
	}