[중급 알고리즘] Brute Force 확장3

💚 2234 성곽 💥

여기서 쟁점은 하나의 벽을 제거해서 얻을 수 있는 가장 넓은 방의 크기를 구하는 일이다.

하나의 벽을 제거할 때는 최대 두 개의 방을 합할 수 있으므로 인접한 방의 크기 합의 최대를 구하면 된다.

따라서 방별로 인접성을 파악한 후 이미 구한 방의 크기를 활용하면 되지 않을까?

 

🎶 딩동댕동~ 앞서 푼 16932 모양만들기 문제와 유사하게 풀면 된다.

이를 위해 각 방의 정보와 해당 위치의 방 정보를 저장하는 작업이 필요하다.

#include <iostream>
#include <queue>

using namespace std;

int n, m;
// 성곽
int a[50][50];
// [i,j]의 방번호
int d[50][50];
// 방 i의 크기
int room[50 * 50];
// 문제에서 안내된 1,2,4,8의 순대로
// 2의 제곱수로 표현 시 지수가 곧 인덱스인 셈
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// rooms: 방번호
int bfs(int x, int y, int rooms) {
    queue<pair<int, int>> q;
    q.push({x, y});
    d[x][y] = rooms;
    int cnt = 0;
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        cnt += 1;
        for(int k = 0;k < 4;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(!inside(nx, ny)) continue;
            // 벽이 있으면 안됨
            if(a[x][y] & (1 << k)) continue;
            if(d[nx][ny] != 0) continue;
            q.push({nx, ny});
            d[nx][ny] = rooms;
        }
    }
    
    return cnt;
}

int main() {
    cin >> m >> n;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }
    
    int rooms = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(d[i][j] == 0) {
                rooms += 1;
                room[rooms] = bfs(i, j, rooms);
            }
        }
    }
    
    cout << rooms << '\n';
    
    int ans = 0;
    for(int i = 1;i <= rooms;i++) {
        if(ans < room[i]) {
            ans = room[i];
        }
    }
    
    cout << ans << '\n';
    
    ans = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            int x = i;
            int y = j;
            // 상하좌우로 모두 탐색할 필요 없음
            // 아래와 오른쪽만 탐색하면 됨
            for(int k = 2;k < 4;k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(!inside(nx, ny)) continue;
                // 이거 중요! 같은 방에 속하는 경우는 탐색할 필요 없음
                if(d[nx][ny] == d[x][y]) continue;
                if(a[x][y] & (1 << k)) {
                    if(ans < room[d[x][y]] + room[d[nx][ny]]) {
                        ans = room[d[x][y]] + room[d[nx][ny]];
                    }
                }
            }
        }
    }
    
    cout << ans << '\n';
}

💚 12906 새로운 하노이 탑

전체 원판 개수의 합이 10개이므로 경우의 수가 그리 많지 않다.(10개를 3개로 나눈다 생각)

특이하게 막대별 조합을 모두 확인해야 하기 때문에 map의 key로 배열을 삼았다.

그리고 해당 조합을 만들어내기 위한 원반 이동 횟수를 value로 정한다.

여기서 유용한 Tip을 찾았다. 평소에 find 메소드를 써서 map에 액세스했다. end()보다는 count 메서드를 쓰면 훨씬 직관적이다.

#include <iostream>
#include <array>
#include <queue>
#include <map>
using namespace std;
int main() {
    // 길이가 3인 string 배열
    // 고정 길이 배열
    array<string, 3> s;
    
    for(int i = 0;i < 3;i++) {
        int cnt;
        cin >> cnt;
        if(cnt > 0) {
            // s[i] : i번 탑의 원판 개수
            cin >> s[i];
        }
        else {
            s[i] = "";
        }
    }
    // 원판 종류별 수 세기
    // cnt[i]: i번 원판의 개수
    int cnt[3] = {0, 0, 0};
    for(int i = 0;i < 3;i++) {
        for(int j = 0;j < s[i].length();j++) {
            cnt[s[i][j] - 'A'] += 1;
        }
    }
    // 각 막대별 원반 상태 array, 원반 이동 횟수
    map<array<string, 3>, int> d;
    queue<array<string, 3>> q;
    
    q.push(s);
    d[s] = 0;
    while(!q.empty()) {
        auto now = q.front();
        q.pop();
        for(int i = 0;i < 3;i++) {
            for(int j = 0;j < 3;j++) {
                if(i == j) continue;
                if(now[i].length() == 0) continue;
                array<string, 3> next(now);
                // i의 가장 위 원반을 j로 옮긴다.
                next[j].push_back(next[i].back());
                next[i].pop_back();
                // find는 불편해서 count를 쓰면 편하다.
                if(d.count(next) == 0) {
                    d[next] = d[now] + 1;
                    q.push(next);
                }
            }
        }
    }
    
    array<string, 3> ans;
    for(int i = 0;i < 3;i++) {
        for(int j = 0;j < cnt[i];j++) {
            ans[i] += (char)('A' + i);
        }
    }
    
    cout << d[ans] << '\n';
    return 0;
}

💚 17141 연구소 2

M개의 바이러스를 놓는 문제 → Brute Force(최대 10개)

모든 칸에 바이러스를 퍼뜨리는 최소 시간 → BFS

 

여기선 재귀 함수를 이용해 M개의 조합을 만들어낸다.

M개에 도달하면 BFS로 바이러스가 모든 칸에 도달할 수 있는지 확인한다.

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

using namespace std;
int n, m;
int a[100][100];
int d[100][100];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int ans = -1;
vector<pair<int, int>> candi;

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

void bfs() {
    memset(d, -1, sizeof(d));
    queue<pair<int, int>> q;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            // 바이러스 위치
            if(a[i][j] == 3) {
                q.push({i, j});
                d[i][j] = 0 ;
            }
        }
    }
    
    while(!q.empty()) {
        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(inside(nx, ny)) {
                // 벽이 아니며 방문한 적 없어야 함
                if(a[nx][ny] != 1 && d[nx][ny] == -1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    int cur = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            // 벽이 아닌 칸 = 빈칸 혹은 바이러스가 놓인 칸
            if(a[i][j]!= 1) {
                if(d[i][j] == -1) return;
                if(cur < d[i][j]) cur = d[i][j];
            }
        }
    }
    
    if(ans == -1 || ans > cur) ans = cur;
}

// index번째를 고를지 말지 결정
void go(int index, int cnt) {
    // 탐색 종료
    if(index == candi.size()) {
        if(cnt == m) {
            bfs();
        }
    }
    else {
        int x, y;
        tie(x, y) = candi[index];
        // 바이러스 위치는 3으로 표시
        a[x][y] = 3;
        // 바이러스 추가 O
        go(index + 1, cnt + 1);
        a[x][y] = 0;
        // 바이러스 추가 X
        go(index + 1, cnt);
    }
}
int main() {
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++) {
            cin >> a[i][j];
            if(a[i][j] == 2) {
                a[i][j] = 0;
                candi.push_back({i, j});
            }
        }
    }
    
    go(0,0);
    cout << ans << '\n';
    return 0;
}

💚 17142 연구소 3

앞선 문제와 약간 다르게 바이러스가 이미 다 있되, 바이러스는 활성/비활성 상태에 놓여 있다.

가장 처음에 모든 바이러스는 비활성 상태이고, 바이러스 M개를 활성 상태로 바꾸려고 한다.

활성 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되고 1초가 걸린다.

비활성 바이러스가 있는 곳으로 활성바이러스가 이동하면 비활성이 활성으로 변한다.

모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제

 

차이 1: 연구소 2는 바이러스를 놓을 수 있는 칸을 후보에 넣고 빈칸으로 변경했다. 연구소 3은 변경하지 않는다.

차이 2: 차이 1 때문에 바이러스를 놓을 칸을 결정할 때, 바이러스를 놓지 않는 경우(활성 바이러스로 바꾸지 않는 경우)를 연구소 2는 0으로 즉 빈칸으로, 연구소 3은 2로 설정한다.(즉 일반 빈칸과 구별)

차이 3: 정답을 구할 때 연구소 2는 벽이 아닌 경우(a[i][j] != 1)거리의 최댓값을 구하고, 연구소 3은 빈 칸인 경우(a[i][j] == 0) 거리의 최댓값을 구한다.

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

using namespace std;
int n, m;
int a[100][100];
int d[100][100];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int ans = -1;
vector<pair<int, int>> candi;

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

void bfs() {
    memset(d, -1, sizeof(d));
    queue<pair<int, int>> q;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            // 바이러스 위치
            if(a[i][j] == 3) {
                q.push({i, j});
                d[i][j] = 0 ;
            }
        }
    }
    
    while(!q.empty()) {
        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(inside(nx, ny)) {
                // 벽이 아니며 방문한 적 없어야 함
                if(a[nx][ny] != 1 && d[nx][ny] == -1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    int cur = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            // 벽이 아닌 칸 = 빈칸 혹은 바이러스가 놓인 칸
            // 차이 3
            if(a[i][j] == 0) {
                if(d[i][j] == -1) return;
                if(cur < d[i][j]) cur = d[i][j];
            }
        }
    }
    
    if(ans == -1 || ans > cur) ans = cur;
}

// index번째를 고를지 말지 결정
void go(int index, int cnt) {
    // 탐색 종료
    if(index == candi.size()) {
        if(cnt == m) {
            bfs();
        }
    }
    else {
        int x, y;
        tie(x, y) = candi[index];
        // 바이러스 위치는 3으로 표시
        a[x][y] = 3;
        // 바이러스 추가 O
        go(index + 1, cnt + 1);
        // 차이 2 - 일반 빈칸이랑 구별해서 비활성화 바이러스임을 표시
        a[x][y] = 2;
        // 바이러스 추가 X
        go(index + 1, cnt);
    }
}
int main() {
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++) {
            cin >> a[i][j];
            if(a[i][j] == 2) {
                candi.push_back({i, j});
                // 차이 1 - 빈칸으로 만들지 않음
            }
        }
    }
    
    go(0,0);
    cout << ans << '\n';
    return 0;
}