[알고리즘] cpp c++ 다리 만들기2

포인트

1. bfs, dfs, 완전탐색을 잘알아야 한다. 설계를 잘한느 것이 중요하다.

2. (입력) -> (라벨링, bfs) ->(다리 만들기) -> (다리 총길이 구하기)

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

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

using namespace std;

int n, m, num, answer = 100;
int map[11][11];                    // 입력 받을 맵
int lable[11][11];                // 각 섬마다 번호를 붙이기 위해 사용한 맵
int dist[7][7];    // 각 섬의 최단거리를 저장하기 위한 배열.

bool visited[11][11];                    // BFS탐색 시, 방문체크를 위한 배열(섬의 번호 붙일 때 사용)
bool Connect[7][7];    // 연결관계 체크를 위한 배열
bool ConnectIsland[7];            // BFS탐색 시, 방문체크를 위한 배열(연결관계를 통해, 정답을 도출하기 위한 BFS탐색 시 사용)
bool Select[7 * 7];    // 조합 추출에서 중복 추출을 막기 위한 배열.


vector<pair<int, int>> islands;                      // 입력 시, 모든 섬의 좌표들을 저장하기 위한 벡터
vector<pair<int, int>> area_position[11 + 1];     // 각 섬에 존재하는 땅의 좌표들을 저장하기 위한 벡터배열
vector<pair<pair<int, int>, int>> bridges; // 섬과 섬을 연결하는 다리의 길이와, 그 다리가 어떤 섬을 연결하는지 저장하기 위한 벡터.

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs(int a, int b, int number) {
    queue<pair<int, int>> q;
    q.push({a, b});
    visited[a][b] = true;
    lable[a][b] = number;
    area_position[number].push_back(make_pair(a, b));

    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (!visited[nx][ny] && map[nx][ny] == 1) {
                q.push({nx, ny});
                visited[nx][ny] = true;
                lable[nx][ny] = number;
                area_position[number].push_back(make_pair(nx, ny));
            }
        }
    } // 이렇게 해서 붙어 있는 섬에 번호를 붙여 준다.
}

void label() {
    int label_number = 1;
    for (int i = 0; i < islands.size(); i++) {
        int x, y;
        tie(x, y) = islands[i];

        if (!visited[x][y]) {
            bfs(x, y, label_number++);
        }
    }
    num = label_number;
}

void go(int x, int y, int dir, int size, int start, int end) { // 사이즈는 다리길이
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (nx < 0 || ny < 0 || nx >= n || ny >= m) return;                // 맵의 범위를 벗어나면 return

    if (map[nx][ny] == 0)
        go(nx, ny, dir, size + 1, start, end);    // 아직 바다라면 계속 탐색.

    if (map[nx][ny] == 1) { // 탐색하려는 정점이 땅이라면
        if (lable[nx][ny] == end) { // 그 땅이 도착섬이라면 ?
            if (size >= 2) { // 다리의 길이가 2이상인지 체크
                if (dist[start][end] > size) { // 최소길이로 갱신
                    dist[start][end] = size;
                    dist[end][start] = size;
                }
                return;
            }
        } else return;    // 도착점이 아닌 다른 섬이라면 return.
    }
}

void make_bridge(int start, int end) {
    /* 시작 섬에 존재하는 모든 땅덩어리 들에서 도착 섬까지 탐색해본다.*/
    for (int i = 0; i < area_position[start].size(); i++) { // 1번에 있는 것들 부터
        int x, y;
        tie(x, y) = area_position[start][i];

        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

            if (map[nx][ny] == 0) // 다음 숫자가 빈공간이면
                go(x, y, j, 0, start, end);
        }
    }
}

bool CheckState() {
    memset(Connect, false, sizeof(Connect));
    memset(ConnectIsland, false, sizeof(ConnectIsland));
    for (int i = 0; i < bridges.size(); i++) {
        if (Select[i] == true) {
            int x = bridges[i].first.first;
            int y = bridges[i].first.second;

            Connect[x][y] = true;    // 선택한 다리가 연결하는 섬들의 연결관계를 표시
            Connect[y][x] = true;
        }
    }

    // 이후 BFS탐색을 통해서 탐색할 수 있는 섬의 갯수를 Count.
    queue<int> Q;
    Q.push(1);
    ConnectIsland[1] = true;

    int IslandCnt = 1;
    bool Flag = false;
    while (Q.empty() == 0) {
        int Cur = Q.front();
        Q.pop();

        if (IslandCnt == num - 1) {
            Flag = true;
            break;
        }

        for (int i = 1; i < num; i++) {
            if (Cur == i) continue;
            if (Connect[Cur][i] == true && ConnectIsland[i] == false) {
                ConnectIsland[i] = true;
                Q.push(i);
                IslandCnt++;
            }
        }
    }
    return Flag;
}

void find() {
    /*
    섬들간의 최단거리를 구하기 위한 함수.
    시작점과 끝점을 정한 후, DFS를 통해서 구현.
    */
    for (int a = 1; a < num; a++) { //1,2  1,3 1,4 이런식으로 해서 구할 수 있게 한다.
        for (int b = a + 1; b < num; b++) {
            make_bridge(a, b);
            if (dist[a][b] == 100) continue; //근데 만약 이게 100이면 넘어간다.
            bridges.push_back(make_pair(make_pair(a, b), dist[a][b]));
            // 다리의 최소거리를 구했으면, bridges 벡터에 다리가 연결하는 2개의 섬과, 그 거리 총 3개의 데이터를 저장.
        }
    }
}

void go2(int index, int cnt, int sum) {
    /* 조합 구현을 통해서 정답을 도출하기 위한 함수.*/
    if (cnt >= 1)    // 1개이상만 뽑았으면 무조건 확인해본다.
    {
        if (CheckState() == true) {
            if (answer > sum) answer = sum;
        }
    }

    for (int i = index; i < bridges.size(); i++) {
        if (Select[i] == true) continue;
        Select[i] = true;
        go2(i, cnt + 1, sum + bridges[i].second);
        Select[i] = false;
    }
}


int main() {

    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            dist[i][j] = 100;
        }
    }

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1) {
                islands.push_back({i, j});// 입력과 동시에, 섬의 좌표들은 모두 저장.
            }
        }
    }
    label();            // 섬의 번호 붙이기
    find();            // 섬 끼리 최단거리 구하기
    go2(0, 0, 0);        // 정답 도출하기

    if (answer == 100) cout << -1 << endl;
    else cout << answer << endl;
    return 0;
}