백준/완전 탐색9

• 

  [백준 1963번 / C++] 소수 경로 dfs를 활용해서 푼 완전탐색 문제이다 #접근방법 먼저 소수인지 아닌지 판별하기 위해서 에네토스테라스의 체 방식으로 체크를 해줬다. (소수가 아닌 것들은 모두 true로 설정하였다. ) 먼저 queue에다가 시작 숫자 4자리와 count 값을 넣어준다. 그리고 숫자 4자리 수에 각 자릿수 마다 0부터 9까지 넣어서 소수이면서 범위 내에 있고 방문하지 않았다면 dfs를 호출한다. 만약 세가지 조건에 하나라도 포함되어있다면 continue 를 해준다. 이후 찾고자 하는 숫자와 같다면 count값을 출력해주고 만약 찾고자 하는 값이 없다면 "Impossible"을 출력해주자. #include #include #include #include #include #include #include using namesp.. 백준/완전 탐색 2022. 3. 25.

• 

  [백준 15649번 / C++] N과 M (1) DFS를 활용해서 완전탐색으로 풀어보자. #접근방법 1. 먼저 n과 m을 입력 받은 후에 level 값을 파라미터 값으로 전달하면서 바로 dfs를 호출한다. 2. level이 m 이 되었을 때는 지금까지 push_back 해서 모은 result값을 출력한다. 3. 그렇지 않다면 1~n 만큼 반복문을 돌리면서 방문 처리되지 않았을 경우, 방문 처리 및 result값 추가하고 dfs를 호출 4. 호출해서 돌아온 후에는 방문처리를 false 하고 result 배열에 넣었던 값을 다시 빼준다. #include #include using namespace std; int n, m; bool visited[10]; vector result; void dfs(int level) { if (level == m) { f.. 백준/완전 탐색 2022. 3. 24.

• 

  [백준 14888번 / C++] 연산자 끼워넣기 완전탐색으로 dfs를 활용해서 풀면된다. +, -, * , / 연산자를 차례대로 넣어보는 것이다. 예를 들어, 1 3 5 라는 숫자가 주어졌고 각 연산자를 하나씩 대입해보자. 1 + 3 = 4 1 - 3 = -2 1 * 3 = 3 1 / 3 = 0 그리고 연산값이 4부터 다시 dfs를 호출해서 연산하면 된다. 4 + 5 = 9 4 - 5 = -1 4 * 3 = 12 4 / 5 = 0 이후에 연산값이 -2 부터 다시 dfs 를 호출해서 연산한다. 이렇게 dfs를 활용해서 완전탐색으로 풀면된다. #include #include #include using namespace std; #define INF 987654321; bool check[123456 * 2+1]; vector v; int result_ma.. 백준/완전 탐색 2022. 3. 17.

• 

  [백준 2529번 / C++] 부등호 완전 탐색 문제이다. #접근 방법 0부터 9까지 반복문을 돌리는 재귀함수를 생성 후 호출. 0부터 9까지 반복문을 돌리면서 부등호가 일치한지, 방문 하지 않았는지 체크하고 부합되면 재귀함수 호출. 부등호의 개수를 넘게되면 max값과 min값을 저장하여 리턴. 스택에 쌓였던 모든 재귀함수가 반환되면 max값과 min값을 출력한다. * min 값이 012 일 때는 12 로 출력되니 이럴 경우 앞에 0을 하나 붙여준다. #include #include #include #include using namespace std; vector v; int visited[10], k; long long max_n=-1; long long min_n=9999999999; void dfs(int cnt, string s, i.. 백준/완전 탐색 2022. 2. 19.

• 

  [백준 1107번 / C++] 리모컨 완전 탐색을 통해 해결하면 되는 문제이다. 1. 0부터 1000000 까지 모든 채널을 확인한다. 2. 각 채널에서 표시되는 숫자값을 하나하나 확인하면서 고장난 것이 하나라도 있으면 반복문을 종료한다. 3. 고장난 것이 없다면 "현재 채널의 길이 + ((절댓값)목표 채널 - 현재 채널) " 최솟값을 구한다. 4. 반복문이 종료된 후 저장된 최솟값과 현재 수빈이가 있는 100 채널에서 + 또는 - 로 이동할 수 있는 최솟값과 비교해서 작은값을 출력하도록 한다. #include #include #include #include #include #include using namespace std; int inf = 1000001; int ch; int n; bool check[10]; int main() { i.. 백준/완전 탐색 2022. 2. 14.

• [백준 14502번 / C++] 연구소 1. 벽을 설치 할 수 있는 경우를 완전탐색으로 구하기 2. 벽을 설치 할 수 있는 경우에 실제 map에 벽으로 만들기 3. bfs 돌리기 4. 안전지역인 영역이 큰 값으로 갱신해나가기 #include #include #include #include #include using namespace std; int map[8][8]; int wall[8][8]; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int max_cnt = -1; int m, n; int path_cnt; queue q; void bfs() { int s_map[8][8]; int visited[8][8] = { 0, }; int cnt = 0; queue birus; for.. 백준/완전 탐색 2022. 1. 28.

• 

  [백준 14620번 / C++] 꽃길 완전 탐색 문제이다. 1. dfs 구현은 동일 2. 현재 지점에서 상하좌우를 돌아봤을 때 맵을 초과했거나 또는 이미 만개한 꽃잎과 겹치는 부분이 있을 경우 continue 3. 위의 조건을 통과하였다면 현재위치 포함 상하좌우 모두 visited 라는 배열에 저장 후 dfs 호출 4. dfs 호출 이후 코드는 visited 배열을 다시 0으로 초기화. (다른 지역에서 꽃이 필 경우도 모두 탐색해야하기 때문) #include #include #include int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; int n; int map[10][10]; int visited[10][10]; int result = INT_MAX; using namespace std; vo.. 백준/완전 탐색 2022. 1. 25.

• [백준 1189번 / C++] 컴백홈 dfs를 활용해서 완전 탐색으로 풀면 된다. 1. dfs 기본 문법을 활용해서 상 하 좌 우에 조건에 부합되면 들어간다. 2. 집의 좌표값과 일치하고 좌표값까지의 distance가 K와 일치하면 cnt+1을 해준다. 3. 재귀 처리후 돌아오면 visited 배열을 0으로 세팅한다. (다른 방향으로 가는 루트도 체크 해줘야하기 때문에 초기화) #include using namespace std; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; int m, n, k; int map[5][5]; int visited[5][5]; int cnt; void dfs(int y, int x, int dis) { if (x == n - 1 && y == 0&&dis==k) .. 백준/완전 탐색 2022. 1. 25.

• 

  [백준 2589번 / C++] 보물섬 완전 탐색 문제이다. 먼저 map이 [3][4] 배열로 주어진다면 {0,0} ~ {2,3} 까지 총 12개의 좌표값을 하나하나 현위치로 판단해서 갈 수 있는 최대 거리를 구하라는 것이다. 즉, bfs() 를 활용해서 현위치에서 바다가 아닌 육지로 갈 수 있는 거리를 계속해서 갱신하고 최댓값을 구해나가는 것이다. map[3][4]가 주어진다고 가정을 하고, "W = 0 , L = 1" 라고 보기 쉽게 숫자로 표현하였다. 그리고 map 크기만큼 check 라는 배열을 생성 해준다. 먼저 {0,3} 지점을 먼저 살펴보자. 다음 그림을 보면 현위치에서 갈 수 있는 길이 있을 때마다 숫자를 갱신해나간다. 모든 맵을 다 살펴보고 나면 최댓값이 3이라는 것을 알 수 있다. 그렇기 때문에 result라는 표에서 {0,.. 백준/완전 탐색 2022. 1. 14.