dfs7 [백준][완전탐색][백트래킹]2529 부등호 c++구현 목차https://www.acmicpc.net/problem/2529문제 문제 구현 방향처음에 makepermutation으로 다 탐색을 할려했었으나 9!^9이라는 말도 안되는 시간에 다시 생각해 보았다.그래서 완전탐색을 이용한 백트래킹을 통해 해결하였다. 간단히 입력 예) 3 를 통해 설명해보면 최대를 구한다했을 때 9를 넣고 탐색한다. 8을 넣고 탐색한다. 7을 넣고 탐색한다. 이므로 차례로 1을 낮추어 본다.8, 7은 이미 썻기 때문에 3을 낮춘 6을 넣는다. 따라서 7 8 9 6이런식으로 백트래킹을 이용해 상태를 복구해 탐색했다. 코드 구현#include #include #include #include #include #include using namespace std;char symbols.. 2024. 7. 1. [백트래킹][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. [백준][dfs] 16234 인구 이동 c++ 구현 목차https://www.acmicpc.net/problem/16234문제 문제 구현 방향종료 조건이 약간 까다로운 문제였다. 그 전 배열과의 비교를 통해 변화가 없을 때 종료 시키면 된다.범위가 작기 때문에 탐색은 dfs를 통해 반복해서 진행해 주어도 시간 초과가 나지 않는다. 코드 구현#include #include #include#include #include using namespace std;int dx[4] = {0, 0, -1, 1};int dy[4] = { 1, -1, 0, 0 };int board[100][100] = { 0 };int ex[100][100] = { 0 };int visit[100][100] = { 0 };vector> v; vector adj[100];int N, L,.. 2024. 5. 11. [백준][dfs] 1068 트리 c++ 구현 목차https://www.acmicpc.net/problem/1068문제 bfs를 통한 풀이 방법https://be-senior-developer.tistory.com/26 [백준] 1068 트리 c++ 구현목차 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어be-senior-developer.tistory.com 문제 구현 방향dfs를 통해 재귀적으로 접근해 리프노드의 수를 누적하는 방식으로 접근해 보았다.전역 변수를 써서 누적할 수도 있었지만 재귀적인 이해를 통해 누적한 지역변수를 이용했다. 코드 구현#inc.. 2024. 5. 4. 이전 1 2 다음 728x90
