DFS2 (BOJ, 1062) 가르침 실패코드 : O(2^n) Time Exceed 문자열을 26비트로 저장 + 개수 count를 비트로 연산은 좋았으나 .. #define _CRT_SECURE_NO_WARNINGS #include int N, K; char s[16]; int str[50]; int ans=0; int cnt; inline int get_size(int v) { int cnt = !!v; while (v &= v - 1)cnt++; return cnt; }; void dfs(int index, int val) { if (index == N) return; if (get_size(val | str[index]) ans)ans = cnt; dfs(index + 1, val | str[index]); cnt--; } dfs(in.. 2020. 1. 28. DFS 1. 방문하지 않은 이웃 정점들 중 선택하여 방문 2. 더 이상 방문할 정점이 없으면 퇴각. 방문 여부(초기값 -1)를 체크하는 정적 배열 전역 변수 필요 void backtrack(state){ visit[state] = 1; // VISITED if ( End_state || Invalid_state) // 종료 혹은 가지치기 return; for (neighbor case) if(visit[neighbor] == -1){ // UNVISITED backtrack(neighbor); } } 재귀를 쓰는 이유 : 주사위 1번의 경우의 수 -> for문 1개가 필요 주사위 2번의 경우의 수 ->for문 2개 필요.. 주사위 n번이면 ?? 재귀의 단점 : 스택 오버플로우 ( 현업에선 거의 안씀 -> 알고리.. 2019. 11. 17. 이전 1 다음