본문 바로가기

백트래킹7

[백준][백트래킹] 1189 컴백홈 c++ 구현 목차https://www.acmicpc.net/problem/1189문제  코드 구현 방향백트래킹을 통해 탐색을 하였다. 거리가 도달할 경우 종료해 가지치기를 해 주었다. 코드 구현#include #include #include #include #include #include using namespace std;int R, C, K;int dx[4] = { 1, -1, 0, 0 };int dy[4] = { 0, 0, 1, -1 };int cnt = 0;int startx, starty, endx, endy;char board[7][7] = { '.', };int visit[7][7] = { 0 };void print() { for (int i = 0; i R - 1 || nx C - 1) cont.. 2024. 7. 2.
[백트래킹][dfs] 1987 알파벳 c++ 구현 목차문제 코드 구현 시 주의점처음에 거리를 인수로 전달하지 않고 전역변수로 해서 틀렸다.그렇게 하면 백트래킹을 했을 때 호출 시점의 값으로 돌아가지 않기때문이다.아래는 잘못된 방식이다.int dx[4] = { 0, 0, 1, -1 };int dy[4] = { 1, -1, 0, 0 };int R, C;char board[22][22] = { 0 };int visit[22][22] = { 0 };int maxd = 1;int d =0;map m;void dfs(int x, int y){ d++; visit[y][x] = d; m[board[y][x]] = 1; for (int i = 0; i = C || ny = R) continue; if (visit[.. 2024. 6. 29.
완전탐색과 백트래킹 c++ 설명 완전 탐색완전 탐색은 말 그대로 모든 경우의 수를 탐색하는 방법으로 브루트 포스라고 불린다(brute-force)완전 탐색의 방법은 반복문과 재귀함수로 나뉜다. 반복문반복문으로 가능하다면 반복문으로 하는 것이 좋다. 재귀함수너무 복잡하거나 어떠한 행위는 반복하는데 매개변수만 수정해서 넘기면 될 것 같은 경우에 시행한다.   예시 문제100이하의 수 조합이 주어질 때 소수가 되는 경우의 수를 모두 구하여라 입력예시:1024 35 38 40 49 59 60 67 83 98 코드 구현#include #include #include #include #include using namespace std;vector v;vector s;bool isPrime(int n) { if (n == 0) return fal.. 2024. 6. 24.
728x90

티스토리툴바