[중급 알고리즘] Brute Force 문제

💚 16988 Baaaaaaaaaduk2(Easy)

시간 복잡도는 크게 2부분을 나뉜다.

돌을 2개 놓는 부분 알아보기$(NM)^2$, 죽일 수 있는 상대 돌의 개수 세기 BFS →$(NM)$

여기서 BFS를 할 때, 내 돌을 기준으로 BFS 탐색을 하는 것이 아니라 상대 돌을 기준으로 탐색한다는 점이 포인트이고, 만약 탐색 중 빈 공간을 만나면 dead로, 유효하지 않음을 처리하는 것도 중요하다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <tuple>

using namespace std;
int n, m;
int a[20][20];
bool check[20][20];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};


int bfs() {
    memset(check, false, sizeof(check));
    int ans = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            // 상대돌만 세면 된다.
            if(a[i][j] == 2 && check[i][j] == false) {
                // 그룹 초기화
                bool dead = true;
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                // 방문 표시
                check[i][j] = true;
                int cur = 0;
                while(!q.empty()) {
                    cur += 1;
                    int x, y;
                    tie(x, y) = q.front();
                    q.pop();
                    for(int k = 0;k < 4;k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        
                        if(0 <= nx && nx < n && 0 <= ny && ny < m) {
                            // 빈틈없이 에워싸야 한다.
                            if(a[nx][ny] == 0) {
                                dead = false;
                            }
                            // 아직 방문하지 않은 상대의 돌
                            else if(a[nx][ny] == 2 && check[nx][ny] == false) {
                                q.push(make_pair(nx, ny));
                                check[nx][ny] = true;
                            }
                        }
                    }
                }
                
                if(dead) {
                    ans += cur;
                }
            }
        }
    }
    
    return ans;
}
int main() {
    cin >> n >> m;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }
    
    int ans = 0;
    
    for(int x1 = 0;x1 < n;x1++) {
        for(int y1 = 0;y1 < m;y1++) {
            if(a[x1][y1] != 0) continue;
            for(int x2 = 0;x2 < n;x2++){
                for(int y2 = 0;y2 < m;y2++) {
                    // 2개의 빈칸 선택 보장
                    if(x1 == x2 && y1 == y2) continue;
                    if(a[x2][y2] != 0) continue;
                    a[x1][y1] = 1;
                    a[x2][y2] = 1;
                    int cur = bfs();
                    if(ans < cur) {
                        ans = cur;
                    }
                    a[x1][y1] = 0;
                    a[x2][y2] = 0;
                }
            }
        }
    }
    
    cout << ans << '\n';
    return 0;
}

💚 15684 사다리 조작

가로선을 최소로 추가해서 i번 세로선의 결과를 i로 만드는 문제

단순히 하나의 선에만 사다리를 놓는 것이 아니라 , 선 사이에 걸쳐서 사다리를 놓기 때문에 특정 선을 기준으로 사다리를 놓는 방향이 오른쪽인지, 왼쪽인지를 함께 저장해야 한다.

여기선 임의로 1이면 사다리의 왼쪽 끝을 저장하는 것, 2이면 사다리의 오른쪽 끝을 저장하는 것이다.

A[r][c] : r번째 가로 위의 c번 세로 선에 가로 선이 있는가

1이면 왼쪽 끝으로, 2면 오른쪽 끝으로 사다리 존재한다고 표시한다.

 

#include <iostream>
#include <vector>


using namespace std;
int w, h;
int garo[100][100];
int start(int c) {
    int r = 1;
    while(r <= h) {
        if(garo[r][c] == 1) {
            c+= 1;
        }
        else if (garo[r][c] == 2) {
            c -= 1;
        }
        r += 1;
    }
    
    return c;
}
bool go() {
    for(int i = 1;i <= w;i++) {
        int res = start(i);
        if(res != i) return false;
    }
    return true;
}
int main() {
    int m;
    cin >> w >> m >> h;
    while(m--) {
        int x, y;
        cin >> x >> y;
        garo[x][y] = 1;
        garo[x][y + 1] = 2;
    }
    
    vector<pair<int, int>> a;
    for(int i = 1;i <= h;i++) {
        // 사다리가 연속되는 것은 불가능
        for(int j = 1;j <= w - 1;j++) {
            if(garo[i][j] != 0) continue;
            if(garo[i][j + 1] != 0) continue;
            a.emplace_back(i, j);
        }
    }
    
    int ans = -1;
    // 추가할 필요 없음
    if(go()) {
        cout << 0 << '\n';
        return 0;
    }
    int len = a.size();
    // 최대 3개 추가 가능
    for(int i = 0;i < len;i++) {
        int x1 = a[i].first;
        int y1 = a[i].second;
        // 해당 위치 뿐만 아니라 양 옆으로도 사다리 없는 경우
        if(garo[x1][y1] != 0 || garo[x1][y1 + 1] != 0) continue;
        garo[x1][y1] = 1;
        garo[x1][y1 + 1] = 2;
        if(go()) {
            if(ans == -1 || ans > 1) {
                ans = 1;
                break;
            }
        }
        for(int j = i + 1;j < len;j++) {
            int x2 = a[j].first;
            int y2 = a[j].second;
            if(garo[x2][y2] != 0 || garo[x2][y2] != 0) continue;
            garo[x2][y2] = 1;
            garo[x2][y2 + 1] = 2;
            if(go()) {
                if(ans == -1 || ans > 2) {
                    ans = 2;
                }
            }
            for(int k = j + 1;k < len;k++) {
                int x3 = a[k].first;
                int y3 = a[k].second;
                if(garo[x3][y3] != 0 || garo[x3][y3 + 1] != 0) continue;
                garo[x3][y3] = 1;
                garo[x3][y3 + 1] = 2;
                if(go()) {
                    if(ans == -1 || ans > 3) {
                        ans = 3;
                    }
                }
                garo[x3][y3] = 0;
                garo[x3][y3 + 1] = 0;
            }
            garo[x2][y2] = 0;
            garo[x2][y2 + 1] = 0;
        }
        garo[x1][y1] = 0;
        garo[x1][y1 + 1] = 0;
    }
    
    cout << ans << '\n';
    return 0;
}

 💚4902 삼각형의 값 ✨💥(어려운 누적합 문제)

값이 변하지 않고 누적적으로 합을 구할 수 있다는 점에서 누적합을 활용한다.

그렇다면 일반적인 배열이 아니라 삼각형의 모양을 띄고 있는 해당 수의 나열에서 어떻게 누적으로 합을 구할 수 있을까?

바로 열 값이 짝수라면 일반적인 삼각형 모양, 홀수라면 뒤집어진 삼각형의 모양을 띄고 있다. 그리고 삼각형을 확장해나가도 꼭짓점 열값의 홀짝은 유지된다. 

#include <iostream>

using namespace std;
int n;
int a[401][801];
int s[401][801];
int ans = 0;
void calc(int row, int left, int right, int sum) {
    if(row < 1 || row > n) return;
    if(left < 1 || right > 2 * row - 1) return;
    // 행별로 합
    sum += s[row][right] - s[row][left - 1];
    if(sum > ans) ans = sum;
    if(left % 2 == 0) {
        // 짝수는 역삼각형
        calc(row - 1,left - 2, right, sum);
    }
    else {
        calc(row + 1, left, right + 2, sum);
    }
}
int main() {
    for(int tc = 1;;tc++) {
        cin >> n;
        if(n == 0) break;
        // 단위 삼각형 값은 최대 1000
        ans = -100000;
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= 2 * i - 1;j++) {
                cin >> a[i][j];
                s[i][j] = s[i][j - 1] + a[i][j];
            }
        }
        
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= 2 * i - 1;j++) {
                calc(i, j, j, 0);
            }
        }
        
        cout << tc << ". " << ans << '\n';
    }
    
    return 0;
}

💚16945 매직 스퀘어로 변경

- 1부터 $N^2$까지 수가 하나씩 채워져 있는 크기가 N * N인 배열이 있고

- 이 배열의 모든 행, 열, 대각선의 합이 같으면 매직 스퀘어라고 한다.

- 크기가 3 * 3인 배열 A를 매직 스퀘어로 변경하는 최소 비용을 구하는 문제

- 수 a를 b로 변경하는 비용은 | a - b |

 

$(N^2)!$의 경우의 수

N은 최대 3이다.

next_permutation을 쓰면 간편하게 순열을 만들 수 있는데, 2차원에서는 적용이 힘드니 1차언으로 만들어 준다.

 

💚16953 A → B

문제 제한을 보면 무려 $10^9$으로 10억개가 나온다. 따라서 무작정 풀면 위험할 수 있다고 처음엔 생각이 든다.

하지만 두 연산 모두 값이 늘어나는 형태이므로 연산이 그리 많지 않다.

예를 들어 1에 2를 30번 곱하면 $10^9$를 넘는다.

즉 모든 경우를 다해봐도 30번보다 적기 때문에 Brute Force가 가능하다.

 

다른 방법이 있다.💥(역방향)💥

A를 B로 바꿀 수 있다면 B의 마지막 자리가 1이거나 짝수가 되어야 한다.

B → A로 만든다고 생각해서 마지막 자리가 1인지 짝수인지 아닌지 살펴보는 방법이 있다.