[알고리즘] DFS / BFS

DFS / BFS

탐색 알고리즘

그래프, 트리 등의 자료구조에서 원하는 데이터가 맞는지 대조하는 과정 반복
⚠️ 노드에 방문했다는 표시가 없으면 무한루프에 빠질 수 있음 !
아래 그림이 전부 트리/그래프 형식이지만 저걸 연결 기준으로 2차원 배열로 만들어서 풀이

DFS = Depth First Search 깊이 우선

루트 노드에서 갈 수 있는 한 끝까지 탐색해 마지막 노드를 방문하고 끝에 다다르면 이전 갈림길로 돌아와 선택하지 않았던 노드를 방문

ex. 미로에서 한 방향으로 갈 수 있을 때까지 가다가 막히면 분기점으로 돌아와서 다른 방향 고

인접 행렬/연결 행렬(2차원 배열)에서는 하나의 노드/칸에 연결된 모든 노드/칸을 방문하고 다음으로 넘어감

재귀 / 스택 자료구조도 활용 가능하지만 재귀가 더 간결하게 작성 가능

void dfs(graph, v, visited) {
	visited[v] = true;
		
	for(auto g:graph[v]){
		if(!visited[g]){
			// 이웃 노드보다 한 노드에 연결된 다음 노드 
			// 호출하는 함수가 먼저 호출됨
			dfs(graph, g, visited);   
		}
	}
}

// main에서 루트노드 호출
dfs(graph, {0, 0}, visited);

stack<v> st;

void dfs(graph, v, visited) {
	visited[v] = true;
	st.push(v);
			
	while(!st.empty()){				
		v ver = st.top();
		st.pop();			// 연결된 노드 전부 스택에 넣기
	}
}
// 근데 이 방법은 그래프 그림상 오른쪽 방향으로 쭉 탐색함

// main에서 루트노드 호출
dfs(graph, {0, 0}, visited);

A → B → D → F → H → L → I → M → P → C → E → G → J → N → K → O

함수 호출 기준
(1, 2) → (2, 1) → (2, 3) → (3, 2) → (3, 4) → (4, 2) → (4, 3) → (4, 5)
→ (5, 1) → (5, 2) → (5, 4) → (4, 6) → (6, 4) → (2, 4) → (2, 5) → (1, 5)

BFS = Breadth First Search 너비 우선

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
ex. 미로에서 갈 수 있는 모든 방향을 확인하는 것이 우선

큐(Queue) 활용FIFO 방식

먼저 들어온 노드의 인접 노드를 모두 확인하고 다음에 먼저 들어온 노드를 확인
⇒ 그래야 한 노드의 모든 인접노드를 확인하고 넘어갈 수 있음

vector<v> ad = {{0,1}, {1,0}, {-1,0}, {0,-1}};
queue<v> q;

void bfs(graph, v, visited) {
	visited[v] = true;
	q.push(v);
		
	while(!q.empty()){
		v ver = q.top();
		visited[ver] = true;
		q.pop();
		
		for(int i=0; i<4; i++){		// ad를 활용해서 사방 확인
			if(...){            // 조건에 맞거나 갈 수 있으면 큐에 넣기
            q.push(...);
		}
	}
}

// main에서 루트노드 호출
bfs(graph, {0, 0} visited);

A → B → C → D → E → F → G → H → I → J → K → L → M → N → O → P

큐에 들어가는 기준
(1, 2) → (1, 5) → (2, 1) → (2, 3) → (2, 4) → (2, 5)
→ (5, 1) → (5, 2) → (5, 4) → (3, 2) → (3, 4)
→ (4, 2) → (4, 3) → (4, 5) → (4, 6)→ (6, 4)

시간 복잡도

모든 노드를 검색한다는 점에서는 시간 복잡도 동일

인접 리스트 O(N+E) | 인접 행렬 **O(N^2)**
N은 노드, E는 간선

인접 행렬 (vector[][])
N만큼 이중 for문 돌려서 두 정점 간에 간선 존재하는지 확인 필요 → O(N^2)

인접 리스트 (LinkedList)
존재하는 간선 정보만 저장 → $간선*2+노드$ 만큼의 시간 복잡도 O(N+E)

비교 및 사례별 사용 이점

DFS
1. 재귀의 경우 자료구조 고려 없이 단순 함수 호출로 처리하여 BFS보다 간단
2. 함수 호출 오버헤드로 단순 검색에서 BFS보다 느림
3. 방문한 노드도 일단 함수를 호출해서 확인한다는 점에서 비효율적

• 모든 노드를 방문하고자 하는 경우에 선택
  • 결정 문제 (~가 가능한지 아닌지)
  • 경로의 가능성 탐색
  • 특정 조건을 만족하는 경로 탐색

BFS
1. 자료구조를 활용하여 DFS보다 빠름
2. 자료구조를 활용하여 DFS보다 복잡함
3. 각 노드를 한 번씩만 방문한다는 점에서 효율적

🚨 거리마다 움직여야하는 이동 수가 같은데 도착점에 다다르면 더 이상의 계산 없이 종료 가능

• 모든 노드를 레벨별로 탐색해야할 때 사용
  • 최단 경로 - DP랑 결합해서 최단 경로를 찾는 경우가 많음
    

문제별 알고리즘 선택

1. 모든 정점 방문
   DFS / BFS 모두 가능
2. 경로의 특징 저장
   DFS 가능
   백트레킹 등을 활용해서 경로의 특징을 확인할 수 있음
   BFS는 각 거리에 있는 정점을 함께 탐색하기 때문에 경로별 특징을 저장할 수 없음
   ex. 정점마다 숫자가 있고 경로에 같은 숫자가 있으면 안된다는 조건이 있는 문제
3. 최단 거리
   DFS / BFS 모두 가능
   BFS가 효율적 (먼저 찾아지는 해답 => 최단거리)

➕ 검색 대상 그래프가 크다면 DFS 고려
반복문으로 인접노드 찾는 것도 오버헤드

➕ 검색 대상 그래프가 크지 않고 구해야하는 거리가 멀지 않다면 BFS 고려
훨씬 효율적인 풀이 가능

문제별 알고리즘 선택 참고 자료