mintuchel mintuchel

전형적인 DFS 사용한 조합론 문제이다. DFS 돌때 자신의 뒤 idx부터 호출하게 하고총 3개이면 조건판단해서 종료되게 하였다. 시간초과를 방지하기 위해3개를 조합하는 과정에서 M을 이미 넘어가게 되면 스킵하게 하였다 #include #include #include #define SIZE 101using namespace std;int N, M;vector arr;int ans = 0;void solve(int idx, int sum, int cnt){ // 종료조건이면 확인하고 return if(cnt == 3){ // 최신화가 안되어있었거나 지금꺼가 M에 더 가까우면 최신화 if (M - ans > M - sum) { ans = s..

DFS만 쓰면 시간초과가 난다따라서 DP로 못가는 경로는 미리 막아두어 다음턴에도 해당 경로로 탐색이 불가능하게 해줘야한다 이미 지나간 경로도 map[newy][newx] = 1 로 마킹하고 길이 없는 경로도 1로 마킹되게 해서 접근하지 못하게 하였다.#include #include using namespace std;int R, C;bitset map[10001];// 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 순서로int dy[3] = {-1, 0, 1};int dx[3] = {1, 1, 1};int dfs(int cury, int curx){ // 종점 도달이면 if (curx == C - 1) { map[cury][curx] = 1; return 1;..

DFS + DP 조합의 문제이다 하지만 맨 처음에는 DFS로 했다가 시간초과DFS + DP로 했다가 40%로 시간초과가 나서 뭐가 문제일까 하고 보니 답이 아닌 경로일때 최적화가 안된다는 문제가 되는걸 알았음 답이 안나오는 경우이면 내 코드 상 동서남북 훓고 sum의 기본값인 0을 반환함따라서 특정 dp 값이 0이면 해당 경로를 이미 탐색해봤는데 종점까지의 경로가 없더라~~ 인거임 그래서 경로가 없는 상황을 나타내는 값이랑 경로 탐색을 한번도 안한 상황을 나타내는 값을 구분하기 위해서탐색을 한번도 안한 상황은 dp값을 -1로경로가 없는 상황은 dp값을 0으로 하기로 함 그래서 초기에 모두 -1로 초기화 해주고 돌려야하고bfs 내부에서 dp값이 0이면 그냥 무시하게 해야함 https://www.acmicp..

유명한 nqueen 문제이다.그냥 백트래킹으로 풀었는데 시간초과나서 틀뜰줄 알았던게 간신히 통과가 되었다 근데 이 풀이는 좋은 풀이가 아니다.nqueen 중 시간이 넉넉한 문제를 풀어서 그렇지 더 빠른 정해들이 있다. 더 빠른 정해는 마지막 코드임. #include #include #include using namespace std;int N;int cnt;void backtrack(int y, vector> queens) { if (y != queens.size()) return; if (y == N) { cnt++; return; } for (int x = 0; x > N; vector> queens; backtrack(0, queens); cout  이건 y=x+k y=-x-N+k 를 사용함무조..

우선 오름차순으로만 뽑으므로 visited는 필요가 없다 왜냐하면 idx에 의해 어떤 원소를 방문했는지 알 수 있기 때문 idx 전꺼를 방문한거고 idx 부터 방문가능한 것들이기 때문 그래서 조합 문제여도 visited가 필요가 없다 그리고 6개가 될 수 없으면 그냥 탐색 자체를 안해주면 된다 그래서 최대로 모았는데도 6개가 될 수 없는 경우에는 그냥 return 해주게 하면 됨 참고로 이걸 모든 오름차순 순열 조합을 다 탐색해서(6개가 아닌 경우도) 6개일 경우만 출력해도 통과는 한다 그 코드는 맨 아래에 있음. 그냥 아예 모든 오름차순 조합을 다 탐색하는 코드 #include #include #include using namespace std; int N; vector v; bitset visited..

영역 카운트를 어떻게 해야할까 고민만 좀 오래했다. 결론적으로 영역 개수는 DFS가 호출된 횟수이다. 우선 rain이 M만큼 올 경우 준비한 2차원 bitset 배열을 통해 침수되는 부분이랑 안전한 부분이랑 영역을 표시해야한다 나는 침수되는 부분은 0 안전한 부분은 1로 함. 그 후에 DFS로 1인 지역만 탐색하게 하면 된다. 여기서 기존에 알고 있는 DFS를 살짝 변형해야한다. 왜냐하면 이게 이미 count된 안전지역을 또 count할 필요는 없기 때문이다. 따라서 DFS로 돌았으면 돌았다는 사실만 기록해주면 되지, 돌고 나서 돌았다는 사실을 번복하지 않아도 된다. 나는 그래서 안전구역 한 구역을 돌았으면 그냥 침수지역으로 인식되게 0으로 바꿔주었다. 이렇게 하면 이어진 안전지역끼리 쭉 돌고 cnt가 ..

stack으로 DFS연습하려고 품 근데 플로이드 워셜 알고리즘으로 푸는 방법도 있다고 한다. 그건 일단 나중에 오늘 술마심 ㅇㅇ 여기서 내가 막판에 놓친게 stack st; st.push(start); ans[node][start] = 1; 여기서 ans[node][start] = 1 쓰는걸 안해서 결과인 ans 배열에 기존으로 입력된 arr 배열에 1이 들어간 부분들을 표시 안되게 했다. 주의요망 ㅇㅇ #include #include #define SIZE 101 using namespace std; int N; int arr[SIZE][SIZE]; int ans[SIZE][SIZE]; void DFS(int node, int start) { stack st; st.push(start); ans[nod..

이 문제는 백트래킹으로 푸는게 정해다. 길따라 가다가 아니다 싶으면 바로 빠져나오는 것이다. 근데 이게 중간에 빠져나오는걸 확인할때 예를 들어 B가 1234 이면 A가 17?? 이면 뒤에 숫자가 뭐가 오든 간에 A는 B보다 무조건 크다는 것을 알 수 있다. 따라서 이걸 함수로 만들면 1000 + 700 해줘서 1700 즉 17?? 중 가장 작은 값이 B보다 작냐? 를 판단해주면 되는데 이 함수 짜서 중간에 박아놓는 것보다 그냥 DFS로 조합 완전탐색 해놓고 마지막 즉 4자리 숫자가 되었을때 딱 한번 확인하고 빠져나오는걸 짜는게 당연히 코드 짜기는 훨씬 쉽다. 숫자도 10^9 이하이니 10자리만 배치하면 되므로 DFS로 끝까지 완전탐색 재귀로 돌린다고 해도 시간제한 안걸림. 일단 완탐으로 통과하긴함. #i..