알고리즘/완전 탐색14 백트래킹 개념 출처 : chanhuiseok.github.io/posts/algo-23/ * 백트래킹 = 되추적 = Backtracking - 유망(promising)하면 탐색을 계속 진행하고, 유망하지 않으면 부모 노드로 다시 돌아가(Backtracking)는 기법 (유망하다 = 해가 될 가능성이 있다) - 다시 말해, 탐색 중 유망성 검사를 통해 가지치기(pruning)를 하는 기법 - DFS는 모든 노드를 탐색하지만, 백트래킹은 모든 노드를 탐색하지 않을 수 있다는 점에서, 성능 차이가 있음 - 자식 노드로 내려갈 때는 방문 표시를 하고, 부모 노드로 올라갈 때는 방문 취소를 함으로써, 방문 여부를 마치 스택처럼 관리해야 하는데, 이는 주로 재귀 함수의 전후에 방문 여부를 변경해주는 식으로 구현한다. (아래와 같.. 2021. 1. 5. 백준 11724번 : 연결 요소의 개수 문제 링크 : www.acmicpc.net/problem/11724 내 풀이(2021.1.3.) : #include #include using namespace std; int visit[1001] = { 0, }; int edge[1001][1001] = { 0, }; int N, M; int cnt = 0; void BFS(int root) { if (visit[root] == 1) return; visit[root] = 1; cnt++; queue q; q.push(root); while (!q.empty()) { int n = q.front(); q.pop(); for (int i = 1; i > N >> M; for (int i = 0; i > u.. 2021. 1. 3. 백준 1012번 : 유기농 배추 문제 링크 : acmicpc.net/problem/1012 내 풀이(2021. 1. 2.) : #include using namespace std; bool exist[50][50]; bool visit[50][50]; int counts = 0; int X, Y, K; void search(int y, int x, bool first) { if (y == -1 || x == -1 || y == Y || x == X) return; if (exist[y][x] == false) return; if (visit[y][x] == true) { return; } else { if (first == true) { counts++; first = false; } } visit[y][x] = true; search.. 2021. 1. 2. BFS 개념 참고 : coding-factory.tistory.com/612 인접 행렬은 노드들 간의 연결 관계가 많을 때 인접 리스트는 노드들 간의 연결 관계가 적을 때 사용한다. Node가 N개이면 Edge의 최대 개수는 1+2+ ... + (N-1) = N(N-1)/2 2020. 12. 21. 이전 1 2 3 4 다음