기록을

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

0~ 최대 높이까지 조합으로 뽑아준다.

뽑은 row들에 대하여 모든 경우로 A와 B로 바꿔주고 검사하는 작업을 해주면 된다.

#include<iostream>
#include<vector>
using namespace std;

int h, w, k, m[14][21], org[14][21], st = 0;

bool used[14], findAns = false;

vector<int> v;

void changeRow(int r, int val) {
    for (int j = 0; j < w; j++)
        m[r][j] = val;
}

void toOrg(int r) {
    for (int j = 0; j < w; j++)
        m[r][j] = org[r][j];
}

void dfs(int cnt) { //순열로
    if (cnt == (int)v.size()) {
        
        //투과율 검사 -> 만족하면 바로종료. 정답은 cnt
        for (int j = 0; j < w; j++) {
            int sameCnt = 0;
            bool contin = false;
            for (int i = 0; i < h-1; i++) {
                if (m[i][j] == m[i + 1][j]) sameCnt++;
                else sameCnt = 0;

                if (sameCnt == k - 1) {
                    contin = true;
                    break;
                }
                
                
            }
            if (!contin) return; //실패지점
            
            else if (contin && j == w - 1) 
                findAns = true; //정답 찾음
        }
        
        return;
    }

        for (int j = 0; j < 2; j++) {
            changeRow(v[cnt], j); //v[cnt]행을 i로 바꾸기
            dfs(cnt + 1);
            if (findAns) return; //정답 나옴
            toOrg(v[cnt]); //v[cnt]행 원상복구
        }
    
}

void pickRow(int cnt, int goal) { //조합
                                  
    if (cnt == goal) {
        
        dfs(0); //무조건 0아니면 1로
        return;
    }

    if (cnt == 0) st = 0;
    for (int i = st; i < h; i++) {
        if (!used[i]) {
            //row[cnt] = i;
            st = i;
            v.push_back(i);
            used[i] = true;
            pickRow(cnt + 1, goal);
            if (findAns) return;
            used[i] = false;
            v.pop_back();
        }
    }
}

void initMap() {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++)
            m[i][j] = org[i][j];
    }
}
int main(void) {

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> h >> w >> k;
        //a면 0, b면 1
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++) {
                cin >> m[i][j];
                org[i][j] = m[i][j]; //원래 배열
            }

    
        int ans = 0;
        for (int i = 0; i < h; i++) {
            pickRow(0, i);
            //초기화
            if (findAns) {
                ans = i;
                break;
            }
            initMap();
        }

        cout << "#" << t << ' ' << ans << '\n';
         
        for (int i = 0; i < h; i++) 
            used[i] = false;

        v.clear();

        findAns = false;
        st = 0;
        
    }

    return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

사용할 수 있는 연산자의 개수를 하나씩 감소시켜보면서 DFS를 수행해주면된다.

사용중 처리를 연산자의 수를 조절해줌으로써 해준다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

연산자의 수가 가령 1,5,0,3

이렇게 주어지면 나는 새로운 벡터에 0을 1개, 1을 5개, 3을 3개 추가하고, 그 백터를 이용해서 순열을 돌렸다.

이 과정에서 중복도 발생하고, set을 사용해서 중복을 처리해주더라도 연산 시간이 소모되기 때문에 시간초과가 나는 것 같다.

따라서, 그냥 1,5,0,3 상태에서, 내가 무언가를 뽑으면 그 원소에 1을 더하거나 빼주고, 양수일 경우에만 뽑을 수 있게 하는 방식으로 DFS를 구현해야 통과할 수 있을 것 같다.

아래는 시간 초과를 받은 코드이다.

https://www.welcomekakao.com/learn/courses/30/lessons/42839

주어지는 문자열에서, 1개~ 문자열길이만큼 숫자를 뽑아서 수를 만들어보고, 소수라면 set에 담는다.

숫자의 중복을 방지하기 위해서 set을 사용했다.

주어진 숫자의 개수만큼 연산자를 결정해주면 된다.

첫번째로 결정된 연산자는 첫번째 사용되는 숫자의 부호를 결정한다고 볼 수 있다.

이후의 연산자는 말그대로 연산자로 생각해서 숫자들을 더하거나 빼주는 계산을 해주면 된다.

백트레킹을 통해서 모든 경우의 수에 대하여 연산자를 결정해준다.

https://www.acmicpc.net/problem/1987

백트래킹을 활용하면 풀리는 문제이다.

현재 DFS에서 거쳐온 지점들을 방문처리, 그리고 그 지점을 거쳐오면서 사용된 문자를 사용처리 해주면서 백트래킹을 진행해주면 된다.

https://www.acmicpc.net/problem/1941

오답에서 적었듯이, 일반적인 dfs로는 해결하기 까다로운 문제이다.

우선, 들어오는 입력만으로는 (y/s)여부 만으로는 그 성분의 자리가 어디인지 알 수 없다.

따라서 자리번호를 매겼다.

그리고 그 자리번호를 7개 선택해서, 뽑힌 7개의 자리번호가 인접한 상태이고, S를 4개 이상 포함한다면 카운트를 해주었다.

순서가 구분이 안 되서 생기는 문제는, 자리번호를 조합으로 뽑으면 순서에 상관없이 하나만 뽑히기 때문에 해결된다.

https://www.acmicpc.net/problem/1941

4방향 dfs 탐색을 활용해서 y가 네개 이하인 경우에만 결과에 포함시키려고 했다.

이렇게 접근하면 자리에 앉아 있는 사람이 y파인지s파인지 말고는 개별적으로 구분할 수 없기 때문에 각자 결과로 나온 문자열을 구분하지 못한다.

가령 sysysys라는 문자열은 맞는 결과이지만, 행렬에서 어떤 위치의 성분을 가져다가 저걸 만들어냈느냐에 따라서 서로 다른 문자열일 수도 있고 같은 문자열일 수도 있다.

아래는 틀린 코드이다.

https://www.acmicpc.net/problem/2023

자리수가 추가될 때마다 현재 상태의 수가 소수인지 아닌지를 판별해주면 된다.

가령 7331을 만들기 위해서, 처음에 7을 골라서 확인하고, 73을 확인하고, 733을 확인하고 ... 이런 흐름이다.

처음에 2를 고르고, 다음에 21이 나왔을텐데, 21은 소수가 아니기 때문에 21#$!@#는 더이상 확인할 필요가 없는 것이다.

신경써줄 부분은, 소수 판별 함수에서 1은 바로 소수가 아님을 반환하는 것과, 가장 큰 자리의 수가 0이 되지 않도록 해주는 부분이다.

https://www.acmicpc.net/problem/2661

1,2,3 세개의 숫자를 활용해서 길이 n의 수열을 만들면 된다.

기본적으로 여기까지는 백트래킹을 활용해서 진행해주면 된다.

이후에 나쁜 수열을 걸러내는 과정에서 substr을 적절히 활용해주면 되겠다.

주의할 점은, 검사를 재귀의 진입 부분에서 해야 한다는 것이다.