백준 17472 - 다리 만들기 2(복습)

문제 링크입니다 https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

BFS와 DFS를 동시에 사용하는 문제였습니다.
 

문제 조건

다리 연결 예시

위와 같은 조건으로 다리를 연결해 건널 수 있는 최소 연결 갯수를 구하는 문제입니다.
 
간단한 문제 접근 방법은
    1. 섬의 구역에 번호 붙이고 좌표 저장하기
    2. A섬에서 B섬까지 갈 수 있는 다리를 구하기
    3. 다리를 연결해주면서 최소수를 구하기
였습니다.
 
문제 접근
     1. 현재 지도의 상태 입력받기
     2. 지도에서 각각의 구역들을 찾기
        2-1. 찾은 구역들에 순서를 표시하기(1번섬, 2번섬...등등)
        2-2. 각 번호의 섬의 좌표를 입력하기
    3. 서로 다른 섬들 간의 다리를 연결하기
    4. 섬들간의 다리 정보를 바탕으로 다리를 하나씩 놓기
        4-1. 다리를 1개 이상 놨을 때 섬 전체를 탐색할 수 있는지 확인하기
    5. 섬 전체를 탐색할 수 있다면 최소 갯수, 아니면 -1를 출력하기
 
 
문제 접근 - 2번
     코드 - get_number()
    일단 2중 for문을 통해서 land[i][j]가 1이라면 BFS를 돌려줍니다. 4방향 탐색 후에 조건에 만족한다면 해당 좌표를 큐에 넣어준뒤에 check에 1를 넣어줌으로써 방문했다고 표시합니다. 또한, 섬의 좌표를 저장하는 백터(island_site)에 해당 섬의 번호안에 좌표를 넣어줍니다.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
문제 접근 - 3번
     코드 - make_bridge(), dfs()
     cost_island라는 이차원 배열을 선언했습니다. 여기에는 가중치를 저장시킬겁니다. 예를 들어서 cost_island[1][2] = 2이라고 한다면 1번 섬과 2번 섬의 다리 길이가 2라는 뜻입니다. 이 배열을 처음에 큰 값으로 전부 저장을 한 뒤에 다리를 연결할 수 있다면 값을 바꿀겁니다.
 
     먼저 1번 섬부터 마지막 섬까지 자신이 갈 수 있는 섬들을 모두 찾을 겁니다. 각각의 섬에는 많은 좌표들이 저장되어 있습니다(island_site 백터). 해당 좌표들에서 한 발짝 나갔을 때 바다라면 이때 DFS를 돌려줍니다 -> make_bridge()
 
     출발한 방향으로 계속 직진했을 때 다른 섬에 도착했다면 그 섬이 자신이 찾는 섬인지를 확인합니다. 자신이 찾는 섬이 맞고, 다리 길이가 2 이상이라면 기존에 저장되어 있던 cost_island[start][finish]의 값과 바교해 min 값을 넣어줍니다.
다른 조건들에 부합하지 않는다면 전부 return해줍니다. -> dfs()
 
     마지막으로 다리의 시작, 끝, 길이를 저장해줍니다(저는 bridge라는 백터에 저장했습니다) 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
문제 접근 - 4번
     코드 - find_link(), check_link()
     지금까지는 각 섬에서 섬까지 최소 다리 길이를 저장했습니다. 이제 이를 활용하겠습니다.  다리를 1개라도 놨을 때 연결이 될 수도 있습니다. 그렇기에 다리를 놓는 수가 1개 이상일 때부터 섬이 전부 연결되었는지를 확인합니다. 연결이 되지 않았더라면 순서대로 다리를 추가합니다 -> find_link()
 
     for문을 다리 갯수만큼 돌려 놓여진 다리를 확인한 뒤, 놓여진 다리가 있다면 connect 배열을 이용해 연결되었다고 해줍니다. 그 후에 1번 섬부터 시작해 연결되어 있는 섬들을 확인합니다. 만약에 연결된 섬의 갯수가 전체 섬의 갯수와 같다면 true를 return, 아니면 false를 return 했습니다 -> check_link()
 
     섬이 전부 연결되었다는 것을 확인했다면 놓인 다리의 최솟값을 저장합니다. 마지막으로 최솟값을 통해서 X또는 -1를 출력합니다.
 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
      
자세한 것은 코드를 참고해주세요!
 

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

int land[11][11];
int island[11][11];
int check[11][11];
int cost_island[7][7];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool Select[50];
bool connect_island[7];
bool connect[7][7];
int N, M;
int ans = 1000001;
int cnt_island = 1;
typedef struct is {
    int x;
    int y;
}is;
vector<is> island_site[7];
typedef struct br {
    int x;
    int y;
    int cost;
}br;
vector<br> bridge;

void get_number(int x, int y, int c) {
    queue<pair<int, int>> q;
    island[x][y] = c;
    island_site[c].push_back({ x,y });
    q.push(make_pair(x, y));
    while (!q.empty()) {
        int x1 = q.front().first;
        int y1 = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x1 + dx[i];
            int yy = y1 + dy[i];
            if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
                if (check[xx][yy] == 0 && land[xx][yy] == 1) {
                    check[xx][yy] = 1;
                    island[xx][yy] = c;
                    island_site[c].push_back({ xx,yy });
                    q.push(make_pair(xx, yy));
                }
            }
        }
    }
    cnt_island++;
}

void dfs(int x, int y, int direction, int cnt, int start, int finish) {
    int xx = x + dx[direction];
    int yy = y + dy[direction];
    if (xx < 1 || yy < 1 || xx > N || yy > M) return;
    if (land[xx][yy] == 0) dfs(xx, yy, direction, cnt + 1, start, finish);
    else if (land[xx][yy] == 1) {
        if (island[xx][yy] == finish) {
            if (cnt > 1) {
                if (cost_island[start][finish] > cnt) {
                    cost_island[start][finish] = cnt;
                    cost_island[finish][start] = cnt;
                }
                return;
            }
        }
        else return;
    }
}

void make_bridge(int start, int finish) {
    for (int i = 0; i < island_site[start].size(); i++) {
        int xx = island_site[start][i].x;
        int yy = island_site[start][i].y;
        for (int j = 0; j < 4; j++) {
            int xxx = xx + dx[j];
            int yyy = yy + dy[j];
            if (xxx >= 1 && yyy >= 1 && xxx <= N && yyy <= M) {
                if (land[xxx][yyy] == 0) dfs(xx, yy, j, 0, start, finish);
            }
        }
    }
}

bool check_link() {
    memset(connect, false, sizeof(connect));
    memset(connect_island, false, sizeof(connect_island));
    for (int i = 0; i < bridge.size(); i++) {
        if (Select[i]) {
            int xx = bridge[i].x;
            int yy = bridge[i].y;
            connect[xx][yy] = true;
            connect[yy][xx] = true;
        }
    }
    queue<int> q;
    connect_island[1] = true;
    q.push(1);

    bool flag = false;
    int cnt_link_island = 1;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (cnt_link_island == cnt_island) {
            flag = true;
            break;
        }
        for (int i = 1; i <= cnt_island; i++) {
            if (now == i) continue;
            if (connect[now][i] && !connect_island[i]) {
                connect_island[i] = true;
                q.push(i);
                cnt_link_island++;
            }
        }
    }
    return flag;
}

void find_link(int a, int cnt, int sum) {
    if (cnt >= 1) {
        if (check_link()) {
          //  cout << sum << " ";
            ans = min(ans, sum);
        }
    }
    for (int i = a; i < bridge.size(); i++) {
        if (Select[i]) continue;
        Select[i] = true;
        find_link(i, cnt + 1, sum + bridge[i].cost);
        Select[i] = false;
    }
}

void solve() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (land[i][j] == 1 && check[i][j] == 0) {
                check[i][j] = 1;
                get_number(i, j, cnt_island);
            }
        }
    }
    cnt_island -= 1;
    for (int i = 1; i <= cnt_island; i++) {
        for (int j = i + 1; j <= cnt_island; j++) {
            make_bridge(i, j);
            if (cost_island[i][j] == 100001) continue;
            bridge.push_back({ i,j,cost_island[i][j] });
        }
    }
    find_link(0, 0, 0);
    if (ans == 1000001) cout << "-1";
    else cout << ans;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> land[i][j];
        }
    }
    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 6; j++) {
            cost_island[i][j] = 100001;
        }
    }
    solve();
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!