[알고리즘] 깊이 우선 탐색 DFS

💡 깊이 우선 탐색 DFS(Depth First Search)란

• 그래프 탐색 방법의 한 가지: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문
• Brute-Force: 완전 탐색 알고리즘으로 가능한 모든 경우의 수를 탐색하고 조건에 맞는 결과만 가져옴
• 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법
• 모든 경로를 방문해야 할 경우 사용에 적합
• 자기 자신을 호출하는 순환 알고리즘의 형태
• 스택 또는 재귀함수를 사용하여 구현

💡 DFS의 순서

    ① 체크인
    ② 목적지에 도착했는가?
    ③ 연결된 곳을 순회
    ④ 갈 수 있는가?
    ⑤ 간다
    ⑥ 체크아웃

• 체크아웃의 개념이 없다면 한 노드를 한 번만 방문한다. 예를 들어 최단 경로를 구한다면 하나의 노드를 여러번 방문해보아야하고, 체크아웃이 필요하다.
  

void search(Node root) {
  if (root == null) return;

  // 1. root 노드 방문
  visit(root);
  root.visited = true; // 1-1. 방문한 노드를 표시

  // 2. root 노드와 인접한 정점을 모두 방문
  for each (Node n in root.adjacent) {
    if (n.visited == false) { // 4. 방문하지 않은 정점을 찾는다.
      search(n); // 3. root 노드와 인접한 정점 정점을 시작 정점으로 DFS를 시작
    }
  }
}

💡 관련 문제: 백준 1062 가르침

    남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

    남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

    첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, K;
int num = 0;
bool alphabet[26];
vector<string> words;

void DFS(int index, int selectedCount) {
//1. 체크인=> visited[index] = true, selectedCount
//2. 목적지인가? selectedCount가 k에 도달했는가 => max 갱신
//3. 연결된 곳을 순회 => index +1 ~26
//4. 갈 수 있는가? => visited[next] == false
//5. 간다 => dfs(next)
//6. 체크아웃 => visited[index] = false, selectedCount 
	if (selectedCount == K) {
		bool isRead;
		int readCount = 0;
		for(int i=0;i<words.size();i++) {
			isRead = true;
			string temp = words[i];
			for(int j=0;j<temp.size();j++) {
				if(alphabet[temp[j] - 'a']==false) {
					isRead = false;
					break;
				}
			}
			if(isRead==true) {
				readCount++;
			}
		}
		num = (readCount>=num) ? readCount : num;
	}
	for(int i=index; i<26; i++) {
		if(alphabet[i]==true) {
			continue;
		}
		alphabet[i] = true;
		DFS(i, selectedCount+1);
		alphabet[i] = false;
	}
}


int main() {
	cin >> N >> K;
	
	for(int i=0;i<N;i++) {
		string s;
		cin >> s;
		words.push_back(s);
	}
	
	if(K<5) {
		cout << 0 << endl;
		return 0;
	}
	
	alphabet['a'-'a'] = true;
	alphabet['n'-'a'] = true;
	alphabet['t'-'a'] = true;
	alphabet['i'-'a'] = true;
	alphabet['c'-'a'] = true;
	K -= 5;
	
	DFS(0,0);
	cout << num << endl;
}

💡 DFS 신장 트리

    무향 연결 그래프에서 깊이 우선 탐색(DFS)로 탐색하면서 생성된 신장 트리(Spanning Tree)

참고 링크1
참고 링크2