알고리즘/완전 탐색13 백준 2178번 : 미로 탐색 문제 링크 : www.acmicpc.net/problem/2178 풀이에 참고한 링크 : www.acmicpc.net/board/view/12343 내 풀이(2021.1.24) : #include #include #include using namespace std; int map[101][101]; int N, M; int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,-1,0,1 }; void show() { for (int i = 1; i 2021. 1. 24. 백준 2667번 : 단지번호붙이기 문제 링크 : www.acmicpc.net/problem/2667 내 풀이(2021.1.13.) : BFS #include #include #include #include using namespace std; int N; vector list; queue q; int map[25][25]; // [y][x] int visit[25][25]; // [y][x] int dy[4] = { 0, -1, 0, 1 }; int dx[4] = { -1, 0, 1, 0 }; void bfs(int y, int x) { int cnt = 0; visit[y][x] = 1; q.push(make_pair(y, x)); while (!q.empty()) { int y = q.front().first; int x = q.fr.. 2021. 1. 13. 백준 15654번 : N과 M (5) 문제 링크 : www.acmicpc.net/problem/15654 내 풀이(2021.1.5.) : #include #include #include using namespace std; vector list; bool visit[8]; int N, M; void search(vector& v) { // 해를 찾음 if (v.size() == M) { for (int i = 0; i < v.size(); i++) { printf("%d ", v[i]); } printf("\n"); return; } // 탐색 for (int i = 0; i < list.size(); i++) { if (visit[i] == true) continue; visit[i] = true; v.push_back(list[i]); .. 2021. 1. 5. 백트래킹 개념 출처 : chanhuiseok.github.io/posts/algo-23/ * 백트래킹 = 되추적 = Backtracking - 유망(promising)하면 탐색을 계속 진행하고, 유망하지 않으면 부모 노드로 다시 돌아가(Backtracking)는 기법 (유망하다 = 해가 될 가능성이 있다) - 다시 말해, 탐색 중 유망성 검사를 통해 가지치기(pruning)를 하는 기법 - DFS는 모든 노드를 탐색하지만, 백트래킹은 모든 노드를 탐색하지 않을 수 있다는 점에서, 성능 차이가 있음 - 자식 노드로 내려갈 때는 방문 표시를 하고, 부모 노드로 올라갈 때는 방문 취소를 함으로써, 방문 여부를 마치 스택처럼 관리해야 하는데, 이는 주로 재귀 함수의 전후에 방문 여부를 변경해주는 식으로 구현한다. (아래와 같.. 2021. 1. 5. 이전 1 2 3 4 다음