예나 지금이나

https://www.acmicpc.net/problem/9663   풀이 과정 백트래킹의 대표적인 문제입니다. 백트래킹은 DFS 또는 BFS를 사용하여 기본적으로 완전탐색을 기반으로 합니다. 다만, 해가 되지 않을 것으로 판단되는 경우에는 더 이상 탐색을 진행하지 않고 다음 탐색을 이어갑니다.  N-Queen의 문제로 예를 들자면, 첫 번째 행에 퀸을 놓았다면 더 이상 첫 번째 행에 다른 퀸들을 놓을 수 없습니다. 서로 공격 대상이 되기 때문입니다. 그렇기 때문에 첫 번째 행에 다른 퀸들을 놓을 수 있는 경우의 수는 탐색하지 않는 것입니다. 이렇게 문제의 해가 되지 않는 경우의 경우 유망하지 않다고 하며, 해가 될 가능성이 있는 경우 유망하다(Promising)고 합니다. 유망하지 않은 노드를 쳐내는 ..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net      풀이 과정 이 문제를 풀기 위해서는 기본적으로 DFS와 BFS 알고리즘을 알아야합니다.DFS란 그래프의 깊이 우선 탐색 알고리즘이고, BFS란 그래프의 너비 우선 탐색 알고리즘을 의미합니다. DFS(깊이 우선 탐색)은 루트 노드에서부터 탐색을 시작해서 하나의 분기가 끝날때까지 타고 내려가서 탐색을 수행한 다음, 탐색이 끝나면 다음 분기로 넘어가서 탐색을 ..