난이도 : 골드 4유형 : BFS / DFS / DP링크 : https://www.acmicpc.net/problem/12869구현 시간 : 30분     문제 풀이 이 문제는 BFS / DFS 알고리즘의 유형으로, 뮤탈리스크는 한 번의 공격에서 세 개의 SCV에 각각 9, 3, 1의 피해를 줄 수 있으며, 세 개의 공격 순서를 자유롭게 선택할 수 있습니다.즉, 모든 가능한 공격 순서를 고려하여 최소 공격 횟수를 찾아야 하는 문제입니다. 얼핏 보면 SCV 체력을 내림차순으로 정렬하고, 9 -> 3 -> 1 순서로 공격하면 쉽게 해결할 수 있지 않나? 싶지만아래 예제를 보면 그리디하게 문제를 해결할 수 없다는 것을 알 수 있습니다.SCV의 체력이 (12 , 10, 4)일 때첫번째 공격 -> 1, 3, 2 ..

깊이 우선 탐색(DFS, Depth-First Search)DFS는 그래프 탐색 알고리즘 중 하나로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하여 차례대로 탐색하는 알고리즘이다. DFS는 주로 스택(Stack)을 통해 구현하거나, 재귀문을 통하여 구현한다.DFS 작동 원리1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다.3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.4. 2 ~ 3번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.   DFS의 작동원리를 이해하기 위해 아래 사진을 준비..