[중급 알고리즘] Brute Froce 확장 2

💚 16956 늑대와 양

최소의 울타리를 구하는 것이 아니므로 사실 BFS를 쓸 필요가 없다.

양과 늑대가 붙어있는 경우를 확인하고, 없으면 모든 빈칸에 울타리를 설치하면 절대로 늑대가 양에게 갈 수 없다.

 

💚5014 스타트링크

처음에 이 문제를 보았을 때는 그냥 BFS 식으로 탐색하는 것이 아니라 건방지게 단순 연산으로 풀 수 있을 것 같았다.

예를 들어 a, b를 각각 위, 아래로 이동가능한 거리라고 가정하자. 2라는 거리를 이동해야할 때, 위로는 2층씩, 아래에는 3층씩 이동가능하다면 $2a + 3b = 2$라는 이차방정식이 세워진다.

여기서 단순히 $a, b$를 구하는 것이 아니라 양의 정수를 구해야하므로 BFS 식으로 탐색을 해야하는 것이 맞았다.

시간복잡도는 최악의 경우 모든 층을 방문하는 것이므로 $O(F)$이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dist[1000001];
bool check[1000001];

// O(F)
int main() {
    int f,s,g,u,d;
    cin >> f >> s >> g >> u >> d;
    queue<int> q;
    q.push(s);
    check[s] = true;
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        if(now + u <= f && check[now + u] == false) {
            dist[now + u] = dist[now] + 1;
            check[now + u] = true;
            q.push(now + u);
        }
        if(now - d >= 1 && check[now - d] == false) {
            dist[now - d] = dist[now] + 1;
            check[now - d] = true;
            q.push(now - d);
        }
    }
    
    if(check[g]) {
        cout << dist[g] << '\n';
    }
    else {
        cout << "use the stairs\n";
    }
    
    return 0;
}

💚9376 탈옥 with Deque for 0 -1 BFS 💥

- 빈 칸, 벽,  문으로 이루어진 지도가 주어진다.

- 두 죄수가 탈옥하기 위해서 열어야 하는 문의 최소 개수를 구하는 문제

 

우선 죄수의 도착점을 만들어줘야 한다. 감옥을 빈칸으로 둘러싸면 된다.

이렇게 되면 테두리는 모두 빈칸이므로 가로막힐 일이 없기 때문에 돌아다는 데 전혀 지장이 없기 때문에 둘러싼 빈칸으로 나왔다고 한다면 두 사람 모두 탈옥했다고 보면 된다. 그리고 문의 개수에도 지장이 없다.

 

그리고 특이하게 시작점이 2개이다. 죄수가 2명이기 때문이다.

그래서 원래 한 명이면 간선의 가중치를 0 또는 1로 두어 BFS 탐색을 하면 되지만 이 문제는 그렇게 풀리지 않는다.

왜냐하면 다른 죄수가 이미 연 문을 또 열면 안되기 때문이다.

 

죄수 1과 죄수 2가 특정 장소에서 모인 후 최종 도착지로 이동한다고 가정하자. 특정 장소는 탈옥 전에 못 만나면, 탈옥 후 바깥 테두리 빈 칸 중 하나일 수도 있다.

A → B = B → A

 

내가 처음에 떠올렸던 방식인 비트마스크로 문의 열림/닫힘 조합으로 경우의 수를 탐색할 경우 지나치게 시간이 많이 걸리기 때문에 BFS로 탐색해야 한다.

 

그래서 밖에서부터, 죄수 1로부터, 죄수 2로부터 각각 지점에서 소요되는 비용을 기록하여 최소의 값을 구하도록 한다.

시간복잡도는 $3NM + NM = O(NM)$이다.(첫 번째에는 각각 BFS에, 두 번째는 최소값 탐색에 쓰인다.)

 

효율적인 탐색을 위해, 지도의 밖에서 BFS 1번, 각 죄수별로 1번씩 BFS를 수행한다.

그 다음 정답으로 세 경우를 모두 더해 최소의 문 여는 방법이 나오는 지점을 구한다.

 

각 죄수별로 - 각 죄수마다 해당 지점까지 가는 데 소요된 비용

지도 밖에서 - 해당 지점에서 지도밖으로 나가는 데 소요된 비용

 

 

이 때 문에서 만나는 경우는 조심해야 한다.

문에서 만나는 경우 비용이 중복되기 때문이다.

 

여기서 deque를 제대로 쓰지 못해서 실수가 발생했다. BFS는 기본적으로 방문되지 않은 구역을 최초 방문하는 게 최소의 경로라는 점이 전제되어있어야 하기 때문이다.

평소의 BFS에서 최소 경로를 찾기 위해서는 일반 Queue를 사용했을 때는 현재 push하는 요소가 이미 queue에 push된 요소보다 비용이 높다는 것을 전제했기 때문에 Queue를 사용하는 것이 가능했다.

 

The Most Basic BFS Code

#include <vector>
#include <queue>

using namespace std;

const int MAX = 1050;
int n,m;
vector<int> v[MAX];
bool check_bfs[MAX];

void BFS(){
  queue<int> q; //Queue 생성
  q.push(0); //초기 시작점 저장
  check_bfs[0] = true; //초기 방문 체크
  
  while(!q.empty()){
    int current = q.front();
    q.pop();
    printf("%d ",current);
    
    for(int i=0;i<v[current].size();i++){
      int next = v[current][i];
      
      if(!check_bfs[next]){
        check_bfs[next] = true;
        q.push(next);
      }
    }
  }
}

 

하지만 이런 문제의 경우 그러한 전제가 지켜지지 않고, 비용이 증가하는 경우와 그대로인 경우를 나누어 자료구조에 요소를 추가해야 한다.

그래서 만약 비용이 추가되지 않은 경우에는 push_back이 아니라 push_front를 쓰는 것이 맞다. 

PS에서는 이러한 변형 알고리즘을 0-1 BFS라고 한다.

만약 여기서 deque이 아니라 총 소요 비용과 함께 저장하면 prority_queue를 쓸 수도 있다. 자연스럽게 자료구조 내에서 정렬이 되어 삽입되기 때문이다. 하지만 priority_queue의 경우 삽입되는 데 $O(logn)$이라는 시간복잡도가 요구되므로, deque보다 비효율적이다.

 

for all v in verticces:
        dist[v] = inf
    dist[start] <- 0
    deque d
    d.push_front(start)

    while d.empty() == false:
        vertex = get front element and pop as in BFS
        for all edges e of form(vertex, u):
            if travelling e relaxes distance to u:
                relax dist[u]
                if e.weight = 1:
                    d.push_back(u)
                else:
                    d.push_front(u)

영어 참고

한국어 참고

 

💚 2251 물통

- 3차원 배열을 만들 필요는 없다.

- 중간에 물이 손실되지 않기 때문에 1,2번 물통에 들어있는 물의 양만 알면 3번 물통의 물 양은 알 수 있기 때문이다.

- 물이 넘치는 경우만 잘 고려하면 된다.

#include <iostream>
#include <queue>

using namespace std;
bool ans[201];
bool check[201][201];
int cap[3];
int from[] = {0, 0, 1, 1, 2, 2};
int to[] = {1, 2, 0, 2, 0, 1};
int main() {
    for(int i = 0;i < 3;i++) {
        cin >> cap[i];
    }
    
    int sum = cap[2];
    // a와 b의 물의 양,
    queue<pair<int, int>> q;
    q.push({0,0});
    check[0][0] = true;
    ans[cap[2]] = true;
    while(!q.empty()) {
        int cur[3];
        cur[0] = q.front().first;
        cur[1] = q.front().second;
        cur[2] = sum - cur[0] - cur[1];
        q.pop();
        for(int k = 0;k < 6;k++) {
            int next[3] = {cur[0], cur[1], cur[2]};
            next[to[k]] += next[from[k]];
            next[from[k]] = 0;
            if(next[to[k]] > cap[to[k]]) {
                next[from[k]] = next[to[k]] - cap[to[k]];
                next[to[k]] = cap[to[k]];
            }
            
            if(!check[next[0]][next[1]]) {
                check[next[0]][next[1]] = true;
                q.push({next[0], next[1]});
                if(next[0] == 0) {
                    ans[next[2]] = true;
                }
            }
        }
    }
    
    for(int i = 0;i <= cap[2];i++) {
        if(ans[i]) {
            cout << i << ' ';
        }
    }
    cout << '\n';
    return 0;
}

💚 16932 모양 만들기 💥

칸 하나 바꿀 때마다 BFS 탐색으로 모양의 최대 크기를 구하면 $O(NM^2)$로 굉장히 비효율적이다.

다른 방법을 강구해야 할 것 같다.

 

우선 바꾸는 경우는 0에서 1, 1에서 0으로 가능하다.

그런데 1에서 0으로 바꾸면 절대로 최대 크기가 나올 수 없다.

그리고 바꾼 수에 인접한 칸에만 영향이 있으므로 전체를 다시 BFS할 필요는 없다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;
int n, m;
int groupn = 0;
int a[1000][1000];
int group[1000][1000];
int group_size[1000 * 1000];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

bool inside(int x, int y){
    return x >= 0&& x < n && y >= 0 && y < m;
}
void bfs(int sx, int sy) {
    groupn += 1;
    queue<pair<int, int>> q;
    q.push({sx, sy});
    group[sx][sy] = groupn;
    int cnt = 1;
    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(group[nx][ny] == 0 && a[nx][ny] == 1) {
                    group[nx][ny] = groupn;
                    q.push({nx, ny});
                    cnt += 1;
                }
            }
        }
    }
    
    group_size[groupn] = cnt;
}
int main() {
    cin >> n >> m;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }
    
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            // 아직 그룹에 속하지 않은 1 BFS 탐색
            if(a[i][j] == 1 && group[i][j] == 0) {
                bfs(i, j);
            }
        }
    }
    
    int ans = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            // 0 근처의 그룹 파악
            if(a[i][j] == 0) {
                vector<int> near;
                for(int k = 0;k < 4;k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    
                    if(inside(nx, ny)) {
                        if(a[nx][ny] == 1) {
                            near.push_back(group[nx][ny]);
                        }
                    }
                }
                // 정렬 후 중복 요소 제거
                // unique: 연속된 중복 원소를 벡터의 제일 뒷부분으로 보낸다.
                sort(near.begin(), near.end());
                near.erase(unique(near.begin(), near.end()), near.end());
                // 0에서 1로 바뀐 스스로 -> 1
                // BFS를 새로 할 필요 없이 인접한 그룹만 탐색하면 된다.
                int sum = 1;
                for(int neighbor : near) {
                    sum += group_size[neighbor];
                }
                // 다른 그룹과 연결되는 경우 최대 크기
                if(ans < sum) ans = sum;
                
            }
        }
    }
    
    cout << ans << '\n';
}

💚 1600 말이 되고픈 원숭이

최솟값을 출력해야 한다. → BFS

단순히 r, c만 기록하는 것이 아니라 나이트의 몇 번째 단계 나갔는지도 기록해야 한다.

#include <iostream>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
//
int dx[] = {0, 0, 1, -1, -2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, -1, 0, 0, 1, 2, 2, 1, -1, -2, -2, -1};
int cost[] = {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1};
int a[200][200];
// 나이트처럼 움직이는 단계도 기록(최대 k번)
// 동작 기록
// 0 ~ 30까지 가능
int d[200][200][31];
int n, m;
bool inside(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}

int main() {
    int l;
    cin >> l;
    cin >> m >> n;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }
    
    memset(d, -1, sizeof(d));
    queue<tuple<int, int, int>> q;
    d[0][0][0] = 0;
    q.push({0, 0, 0});
    while(!q.empty()) {
        int x, y, c;
        tie(x, y, c) = q.front();
        // cout << x << y << c << endl;
        q.pop();
        for(int k = 0;k < 12;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 나이트처럼 이동하는 거면 cost + 1
            int nc = c + cost[k];
            
            if(inside(nx, ny)) {
                // 장애물이 있는 경우 통과
                // 나이트의 수에 상관없이 다 방문해봐야함
                // 무조건 나이트 수가 많다고 이동횟수가 적은 것이 아니기 때문
                if(a[nx][ny] == 1) continue;
                if(nc <= l) {
                    // 방문한 적 없어야 함
                    if(d[nx][ny][nc] == -1) {
                        // 문제의 기준은 나이트 횟수가 아니라 이동횟수이기 때문에 일반적인 queue 사용 가능
                        // queue 진입 순서가 최저로 보장되기 때문
                        d[nx][ny][nc] = d[x][y][c] + 1;
                        q.push({nx, ny, nc});
                    }
                }
            }
        }
    }
    
    int ans = -1;

    // 최소한의 동작 != 최소한의 나이트 이동 횟수
    for(int i = 0;i <= l;i++) {
        // 방문한 적 없으면 패스
        if(d[n - 1][m - 1][i] == -1) continue;
        if(ans == -1 || ans > d[n - 1][m - 1][i]) {
            ans = d[n - 1][m - 1][i];
        }
    }
    
    cout << ans << '\n';
    return 0;
}

💚 4991 로봇 청소기 💥

- 더러운 칸 방문 순서를 어떻게 할 것인가? 어떤 순서로 방문해야 최소 이동 횟수를 보장할 수 있을까?

- 풀이를 크게 나누면

1) 한 칸에서 다른 칸으로 이동하는 최소 이동횟수 ? BFS

2) 청소하는 순서는? 걍 순열로 다 해보는 수밖에 없나? 맞다..;;

 

b 배열 vector<pair<int, int>>: i 번 더러운 칸의 위치

d 배열 vector<vector<int>> : i번 ~ j번 더러운 칸의 거리

 

어차피 더러운 칸의 위치는 변하지 않고, 순서만 변하기 때문에 거리를 미리 기록하면 매번 BFS할 필요가 없다.

자꾸 i로 입력해야하는 부분에 l로 입력해서 메모리 오류가 발생한다.
잘 보고 타이핑하자
Typo ❌ !!

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, m;

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
vector<vector<int>> bfs(vector<string> &a, int sx, int sy) {
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 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(dist[nx][ny] == -1 && a[nx][ny] != 'x') {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    
    return dist;
}

int main() {
    while(true) {
        cin >> m >> n;
        if(n == 0 && m == 0) break;
        vector<string> a(n);
        for(int i = 0;i < n;i++) {
            cin >> a[i];
        }
        // 맨 처음에는 로봇 위치
        // 그 뒤부터는 더러운 칸
        vector<pair<int, int>> b(1);
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                if(a[i][j] == 'o') {
                    b[0] = make_pair(i, j);
                }
                else if(a[i][j] == '*') {
                    b.push_back({i, j});
                }
            }
        }
        // 출발점 + 도착점들
        int l = b.size();

        vector<vector<int>> d(l, vector<int>(l));
        bool ok = true;
        // 출발점과 도착점 간의 거리를 각각 기록
        for(int i = 0;i < l;i++) {
            // 출발점을 중심으로 가능한 모든 구역의 거리 계산
            // 2차원 벡터 리턴
            auto dist = bfs(a, b[i].first, b[i].second);
            for(int j = 0;j < l;j++) {
                // i부터 j까지의 거리 기록
                d[i][j] = dist[b[j].first][b[j].second];
                // 방문 불가능한 더러운 구역이 존재
                if(d[i][j] == -1) {
                    ok = false;
                }
            }
        }


        if(!ok) {
            cout << -1 << '\n';
            continue;
        }
        // 순열을 만드는 벡터
        vector<int> p(l - 1);
        int ans = -1;
        for(int i = 0;i < l - 1;i++) {
            p[i] = i + 1;
        }

        do {
            // 0번(출발지)부터 p[0]까지
            int now = d[0][p[0]];
            for(int i = 0;i < l - 2;i++) {
                now += d[p[i]][p[i + 1]];
            }

            if(ans == -1 || ans > now) {
                ans = now;
            }
        } while(next_permutation(p.begin(), p.end()));

        cout << ans << '\n';
    }

    return 0;
}

💚 2151 거울설치 💥💥💥💥

해당 문제만 보면 사실 잘 이해가 안된다. 안되는 게 맞다.

문제의 조건이 너무 부족해서 문제만 읽고 나면 만약 거울이 서로 마주본다면?

이런 의문이 자연스럽게 생긴다. 물론 이러한 의문을 해소하는 장치로 거울이 반드시 45도로 설치된다고 하지만, 솔직히 충분하진 않은 것 같다..

 

하지만 나는 추가적인 안내를 제공하는 강의를 들으면서 문제를 풀고 있고, 해당 문제의 질문에 추가 조건을 요구하는 질문이 이미 올려져있지만 개선되지 않았기 때문에 그냥 풀었다...

 

거울의 기능은 곧 방향 꺾기이다.

즉 방향을 최소한으로 꺾어야 한다.

앞선 문제와 비슷하게 단순 이동 BFS가 아니라, 랜드마크 위주로 거리를 파악하여 특수한 BFS 탐색을 한다.

각각의 거울마다 네 방향에 대해서 다음 거울을 미리 찾아야 한다.

그 다음, 각각의 거울만 가지고 BFS 탐색을 수행해야 한다. 

이를 통해 단순히 이동횟수가 아니라 문제에서 요구하는 거울 갯수를 카운트하도록 한다.

 

그렇다면 거울 간의 거리는 어떻게 파악하는 것이 좋을까?

바로 앞선 문제와 동일하게 거울마다 번호를 붙여 2차원 배열로 d[i][j] 같이 i부터 j까지의 거리를 기록한다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n;
bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

int main() {
    cin >> n;
    vector<string> s(n);
    vector<vector<int>> b(n, vector<int>(n));
    vector<pair<int, int>> v;
    // 문 번호 기록
    // v: 문 번호마다의 문 위치 기록
    // b[i][j] : (i,j)에 위치한 문의 번호 기록
    int start = -1, end = -1;
    for(int i = 0;i < n;i++) {
        cin >> s[i];
        for(int j = 0;j < n;j++) {
            if(s[i][j] == '#') {
                // 한 쪽 문
                if(start == -1) {
                    start = v.size();
                }
                // 다른 쪽 문
                else {
                    end = v.size();
                }
                v.push_back({i, j});
                b[i][j] = v.size() - 1;
            }
            else if(s[i][j] == '!') {
                v.push_back({i, j});
                b[i][j] = v.size() - 1;
            }
        }
    }
    // 거울의 개수 + 문의 개수
    int m = v.size();
    // 거울, 문 간의 연결성 파악(상하좌우)
    vector<vector<bool>> a(m, vector<bool>(m, false));
    for(int i = 0;i < v.size();i++) {
        for(int k = 0;k < 4;k++) {
            int x = v[i].first + dx[k];
            int y = v[i].second + dy[k];
            while(inside(x, y)) {
                // 빛이 통과할 수 없는 벽
                if(s[x][y] == '*') break;
                if(s[x][y] == '!' || s[x][y] == '#') {
                    // i번 거울/문과 b[x][y] 번 거울/문은 연결
                    // 어차피 반사 방향은 임의로 정해지기 때문에 상관 없음
                    // 각각의 거울마다 상하좌우로 다음 거울을 미리 찾아야 한다.
                    a[i][b[x][y]] = true;
                }
                x += dx[k];
                y += dy[k];
            }
        }
    }
    
    queue<int> q;
    vector<int> dist(m, -1);
    q.push(start);
    dist[start] = 0;
    
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        for(int i = 0;i < m;i++) {
            // i에 최초 방문하고 now와 연결
            if(a[now][i] && dist[i] == -1) {
                dist[i] = dist[now] + 1;
                q.push(i);
            }
        }
    }
    
    cout << dist[end] - 1 << '\n';
    return 0;
}