[알고리즘] Graph Search Algorithm - BFS, DFS

Graph Search Algorithm

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한번씩 방문하는 것이 목적이다.
근데 그래프의 데이터는 배열처럼 정렬되어있지 않다. 그래서 원하는 자료를 찾으려면 하나씩 모두 방문해서 찾아내야한다.

그래프의 모든 정점 탐색 방법에는 여러가지가 있다. 그중 가장 대표적인 방법은 BFS와 DFS이다.
(데이터를 탐색하는 순서가 다른거고, 모든 자료를 하나씩 확인해본다는 점은 같다.)

---

BFS (Breadth - First Search)

Breadth - First Search 말 그대로 너비 우선 탐색. 너비를 우선적으로 탐색하는 방법이다.
한 정점을 기준으로 해당 기준에서 인접한 정점을 모두 방문한 후에, 방문한 정점을 기준으로 변경하고, 변경된 기준에서 인접한 정점을 차례대로 방문한다.

BFS는 Queue 자료 구조를 활용하여 구현된다. (먼저 들어온게 먼저 나가는)
그렇기때문에 시작 정점을 Queue에 삽입한 후, 인접한 정점을 Queue에 차례대로 삽입하면서 탐색을 진행한다.

BFS의 특징

• 루트 정점에서부터 거리가 가까운 정점을 먼저 방문하므로, 최단 경로 탐색에 유리하다.
  (주의 ‼️ Queue에 정점을 삽입할 때 해당 노드까지의 거리를 기록하는 변수를 사용해야하는 경우도 있다.)

• 방문한 정점들을 저장해야하는 경우 메모리 사용이 커진다.
  (방문한 정점들을 Queue에 저장하고 있어야하기 때문에, 그래프의 크기가 크면 Queue에 저장되는 정점들의 수가 많아져서 메모리 사용이 커진다. 따라서 그래프의 크기가 큰 경우에는 BFS 보다 DFS를 사용해야한다.)

• 그래프의 크기와 밀도에 따라서 성능이 달라진다.
  (그래프의 밀도가 높으면 = 간선의 개수가 많으면 -> BFS의 성능이 저하된다.
  그래프의 크기가 크면 = 정점의 개수가 많으면 -> BFS의 성능이 저하된다. )

• 시작 정점에서 도달할 수 없는 정점에 대해서는 탐색하지 않는다.
  따라서 시작 정점에서 도달할 수 있는 정점들만 탐색할 때 사용한다.

• visited 배열과 같은 방문 여부를 체크하는 자료 구조를 사용해야한다.
  (방문 여부를 체크하는 자료구조를 사용하지 않으면 무한 루프에 빠질 수 있다.)

BFS 구현 방법
시작 노드를 Queue에 삽입한 후, 인접한 노드를 Queue에 순차적으로 삽입하면서 탐색을 진행한다. (주의 !! 방문 여부를 확인하는 자료구조를 꼭 사용해야한다. 또한 정점을 Queue에서 꺼낼 때 Queue가 비어있는지 확인한 후에 꺼내야한다.)

1. BFS는 Queue 자료 구조를 활용하여 구현된다.
2. 시작 노드를 Queue에 삽입한 후, Queue가 빌 때까지 반복한다.
3. Queue에서 현재 정점을 가져온다. (queue.poll() 활용)
4. 현재 정점은 이미 이동했다고 방문 여부를 체크한다. ex) visitied[index] = true;
5. poll()을 활용해 가져온 정점을 기준으로, 인접한 정점을 모두 Queue에 삽입한다.(queue.offer() 활용)
6. 다시 반복으로 돌아와서, Queue가 빌 때까지 인접한 정점을 모두 Queue에 삽입하며 그래프를 끝까지 순회한다.

/**
     * BFS 인접행렬 : 너비 우선 탐색을 구현한 템플릿 예제입니다.
     *
     * @param array : 각 정점을 행/열로 하고, 연결된 정점은 1로, 연결되지 않은 정점은 0으로 표기하는 2차원 배열
     * @param visited : 방문여부 확인을 위한 배열
     * @param src : 방문할 정점
     * @param result : 방문했던 정점 리스트를 저장한 List
     *
     **/
    public ArrayList<Integer> bfs_array(int[][] array, boolean[] visited, int src, ArrayList<Integer> result) {
			//bfs의 경우 큐를 사용합니다.
	    Queue<Integer> queue = new LinkedList<>();
			//시작 지점을 큐에 넣어주고, 해당 버택스의 방문 여부를 변경합니다.
	    queue.offer(src);
	    visited[src] = true;
			//큐에 더이상 방문할 요소가 없을 경우까지 반복합니다.
	    while (!queue.isEmpty()) {
				//현재 위치를 큐에서 꺼낸 후
	      int cur = queue.poll();
				// 현재 방문한 정점을 result에 삽입합니다.
				result.add(cur);
				//전체 배열에서 현재 버택스의 행만 확인합니다.
	      for (int i = 0; i < array[cur].length; i++) {
					//길이 존재하고, 아직 방문하지 않았을 경우
	        if(array[cur][i] == 1 && !visited[i]) {
						//큐에 해당 버택스의 위치를 넣어준 이후
	          queue.offer(i);
						//방문 여부를 체크합니다.
	          visited[i] = true;
	        }
	      }
	    }
			//이어진 모든 길을 순회한 후 방문 여부가 담긴 ArrayList를 반환합니다.
	    return result;
  }

BFS를 활용해야하는 경우

• 단순히 그래프의 모든 정점을 방문하는 것이 중요한 문제라면 DFS나 BFS중 편한 거 사용해도 된다.

• 최단거리 구하는 문제
  미로 찾기, 최단 경로 찾기 같은 문제에 BFS를 활용한다.

• 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않은 경우
  최단 경로가 존재한다면, 어느 한 경로가 무한히 이어진다해도 방문 여부와 모든 경로를 확인하기 때문에 반드시 최단 경로를 찾을 수 있다.

---

DFS (Depth - First Search)

Depth - First Search 말 그대로 깊이 우선 탐색. 하나의 경로를 끝까지 탐색한 후, 원하는 목적이 아니라면 다음 경로로 넘어가 탐색한다.
한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.

DFS는 Stack 자료 구조 또는 재귀를 이용해서 구현할 수 있다.

DFS의 특징

• BFS보다 시간이 오래걸릴지라도 모든 노드를 완전히 탐색할 수 있다.
  그래서 제일 첫번째 경로에 답이 있어도 다른 모든 경로를 살펴봐야한다.

• 현 경로상의 정점들만 기억하면 되므로 저장 공간의 수요가 비교적 적고, 목표한 정점이 깊은 단계에 있으면 해를 빨리 구할 수 있다는 장점이 있다.

• 모든 정점을 방문할 수 있도록 시작 정점을 선택해야한다.

• 그래프 내의 순환 구조 (Cycle)를 고려하여 방문한 정점을 확인해서 이미 방문한 정점을 다시 방문하지 않도록 해야한다.
  (주의 !! 도달한 정점이 없다면 무한 루프에 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표한 정점을 발견하지 못하면 다음 경로를 따라 탐색하는 방법을 활용할 수 있다.)

• 목표한 정점에 이르는 경로가 다수일 경우 DFS는 목표한 정점에 최초로 다다르는 순간 탐색을 끝내므로, 이때 얻어진 값이 최적의 결과가 아닐 수 있다.

DFS 구현 방법

1. Stack 자료 구조나 재귀를 통해 구현할 수 있다. (일반적으로 재귀를 통해 구현)
2. 방문했던 정점인지 확인힌다. 방문했다면 재귀 호출을 종료한다.
   2.1 단순 출력이 아닌, 방문 여부를 저장할 데이터가 필요하다면 해당 데이터에 방문 여부를 저장한 후, 저장한 데이터를 반환한다.
3. 방문하지 않았다면, 방문 여부를 체크한다. ex) visitied[index] = true;
4. 해당 정점에 연결된 모든 정점을 재귀호출로 순회한다.

/**
     * DFS 인접행렬 : 깊이 우선 탐색을 구현한 템플릿 예제입니다.
     *
     * @param array : 각 정점을 행/열로 하고, 연결된 정점은 1로, 연결되지 않은 정점은 0으로 표기하는 2차원 배열
     * @param visited : 방문 여부 확인을 위한 배열
     * @param src : 방문할 정점
     * @param result : 방문했던 정점 리스트를 저장한 List
     *
     **/
    public ArrayList<Integer> dfs(int[][] array, boolean[] visited, int src, ArrayList<Integer> result) {
				// 이미 방문했다면
        if (visited[src] == true) {
					result.add(src);    // 방문한 정점을 저장
					return result;      // 저장한 데이터를 반환하며, 재귀호출을 종료
				}

				// 아직 방문하지 않았다면
        visited[src] = true;           // 방문한 정점을 표기
        
				// 현재 정점에서 이동할 수 있는 정점을 순회하며 재귀 호출
        for (int index = 0; index < array.length; index++) {
            if (array[src][index] == 1) {
								// 재귀 호출을 통해, 방문 여부를 담은 데이터를 반환과 동시에 할당
                result = dfs(array, visited, index, result);
            }
        }
				return result;
    }

DFS를 활용해야하는 경우

• 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS,BFS 둘 중 편한 방법을 사용하면 된다.

• 경로의 특징을 저장해둬야하는 문제에 활용한다. (탐색 중에 장애물이 있는 경우도 포함)
  (ex_각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안되는 문제 등, 각각의 경로마다 특징을 저장해둬야할 때에 DFS 사용. BFS는 경로의 특징을 가지지 못하니까)

• 자동 미로 생성과 같은 문제에서 활용한다.

• 검색 대상 그래프가 정말 크다면 DFS를 고려해야한다.
  단지 현 경로상의 정점들만 기억하면 되므로 저장 공간의 수요가 비교적 적고, 목표한 정점이 깊은 단계에 있으면 방문할 수 있는 루트를 빨리 구할 수 있는 장점이 있다.