[17472번] 다리 만들기 2(C++, 삼성 상시 테스트, 쉬운 설명)

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

이 문제는 삼성 상시 테스트 A형 기출 문제이다.

 

문제 접근법.

1. 섬과 섬 사이에 다리를 놓을 수 있는 경우의 수를 전체 탐색해야 한다. 우선, 다리를 놓을 수 있는 경우를 파악해야 한다. 다리를 놓을 수 있는 경우는, 각 섬에서 최소의 다리의 길이를 구해야 한다. 주의해야할 점은, 다리의 길이는 1보다 커야 한다. 즉, 다리의 길이가 1이라면 무시해야 한다. 이 말은 무슨 말이냐면, 만약에 섬 A와 섬 B가 이어질 수 있는 다리의 값이 1과 2만 등장한다면, 최솟값을 2로 선택해야 한다는 것이다.

 

2. 다리를 연결하기 위해서 섬을 이루고 있는 행과 열 값들을 배열에 저장해서, 다른 섬과 최소 거리 다리를 찾아준다. DFS를 이용해서, 섬을 예제처럼 숫자로 구분해준다. 아마, 숫자로 구분하는 것이 힌트로 보인다.

 

3. 연결된 섬 2개의 정보와 길이를 저장하기 위해 구조체를 선언해야 한다. 이 구조체를 저장하기 위한 자료구조에서 조합을 만들기 위한 함수를 작성한다. 선택된 아이템들만을 이용해서 연결 관계를 규정하고, 임의의 아이템를 큐에 넣어서, 연결 관계를 파악한다. 예를 들어서, 선택된 아이템이 [1, 3, 2], [2, 4, 3]이라고 하면, 각 아이템은,

 

섬 1과 섬 3을 연결하기 위해서 다리 길이 2이 필요.

섬 2와 섬 4를 연결하기 위해서 다리 길이 3이 필요.

 

를 의미한다. 

 

조합을 이용한 연결 관계를 2차원 배열로 그려보면,

 

   1 2 3 4

1 0 0 1 0

2 0 0 0 1

3 1 0 0 0

4 0 1 0 0

 

다음과 같다, 1, 2, 3, 4는 섬의 번호를 의미한다.

 

또한 큐 방문 유무를 파악하기 위해서, 섬 방문 체크 배열을 선언한다

 

1 2 3 4

0 0 0 0

 

큐에 처음에 어떤 아이템을 넣어도 상관없다. 어떤 아이템이라도 연결되어 있다면, 섬들을 모두 방문할 수 있을 것이다.

 

만약에 큐에 1을 넣었다고 가정하면, 

 

방문 배열은,

 

1 2 3 4

1 0 0 0

방문한 섬의 수 : 1

 

이 된다. 조합을 이용한 연결 관계를 보면, 1은 3과 연결이 되어 있다. 큐에 3을 넣어주고, 섬 3을 방문했다고 방문 배열에 표시한다.

 

1 2 3 4

1 0 1 0

방문한 섬의 수: 2

 

3에서 시작해서, 닿을 수 있는 섬의 수는 없다. 방문한 섬의 수가 4가 되기도 전에 큐 함수가 종료되었으므로, 선택된 아이템들로만 모든 섬이 연결하게 할 수 없다는 것을 의미한다.

 

유의할 점

1. 섬 사이에 다른 섬이 존재하면 안된다.

2. 다리 길이가 1이 되는 경우를 제외시켜서, 최소 다리 길이를 구할 때 1이 나오지 않도록 한다.

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
typedef struct item {
    int node1, node2, len;
    item(int _n1, int _n2, int _len) :node1(_n1), node2(_n2), len(_len) {};
}item;
int N, M;
int op[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int map[11][11] = { 0 };
int check[11][11] = { 0 };
int visit[7] = { 0 };
int answer = -1;
vector<pair<int, int>> isl[7];
vector<item> i_v;
int sol[36];
int g_idx;
 
void comb(int cnt, int idx) {
    if (idx == i_v.size()) {
        // Check all visit
        int visit[7];
        memset(visit, 0, sizeof(visit));
 
        int result = 0;
        int cnt_visit = 0;
 
        int comb_check[11][11] = { 0 };
        queue<int> q;
 
        for (int i = 1; i < cnt; i++) {
            int n1 = i_v.at(sol[i]).node1;
            int n2 = i_v.at(sol[i]).node2;
            int len = i_v.at(sol[i]).len;
 
            if (q.empty()) {
                q.push(n1);
                visit[n1] = 1;
                cnt_visit = 1;
            }
 
            comb_check[n1][n2] = 1;
            comb_check[n2][n1] = 1;
            result += len;
        }
 
        // Connect Check
        while (!q.empty()) {
            int item = q.front();
            q.pop();
 
            for (int i = 1; i < g_idx; i++) {
                if (visit[i] == 0 && comb_check[item][i] == 1) {
                    visit[i] = 1;
                    cnt_visit++;
                    q.push(i);
                }
            }
        }
 
        if (cnt_visit == g_idx - 1) {
            if (answer == -1)
                answer = result;
            else
                answer = min(answer, result);
        }
        return;
    }
 
    sol[cnt] = idx;
    comb(cnt + 1, idx + 1);
    comb(cnt, idx + 1);
}
void dfs(int r, int c, int idx) {
    for (int dir = 0; dir < 4; dir++) {
        int n_r = r + op[dir][0];
        int n_c = c + op[dir][1];
 
        if (n_r < 1 || n_c < 1 || n_r >N || n_c > M || check[n_r][n_c] == 1 || map[n_r][n_c] != 1)
            continue;
 
        check[n_r][n_c] = 1;
        map[n_r][n_c] = idx;
        isl[idx].push_back(make_pair(n_r, n_c));
        dfs(n_r, n_c, idx);
    }
}
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            check[i][j] = 0;
        }
    }
 
    // Numbering
    g_idx = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (check[i][j] == 0 && map[i][j] == 1) {
                check[i][j] = 1;
                map[i][j] = g_idx;
                isl[g_idx].push_back(make_pair(i, j));
                dfs(i, j, g_idx);
                g_idx += 1;
            }
        }
    }
 
    // Find Minimum Length
    memset(check, 0, sizeof(check));
    for (int i = 1; i < g_idx; i++) {
        for (int j = i + 1; j < g_idx; j++) {
            int result = 0;
            for (int idx1 = 0; idx1 < isl[i].size(); idx1++) {
                for (int idx2 = 0; idx2 < isl[j].size(); idx2++) {
                    int con_check = 0;
                    if (isl[i].at(idx1).second == isl[j].at(idx2).second)
                    {
                        int tmp1 = min(isl[i].at(idx1).first, isl[j].at(idx2).first);
                        int tmp2 = max(isl[i].at(idx1).first, isl[j].at(idx2).first);
                        int tmp_c = isl[i].at(idx1).second;
                        for (int idx3 = tmp1 + 1; idx3 < tmp2; idx3++) {
                            if (map[idx3][tmp_c] != 0) {
                                con_check = 1;
                                break;
                            }
                        }
 
                        if (con_check == 1)
                            continue;
 
                        int dis = abs(tmp1 - tmp2);
                        if (dis == 2)
                            continue;
 
                        if (result == 0) {
                            result = dis;
                        }
                        else {
                            result = min(result, dis);
                        }
                    }
                    else if (isl[i].at(idx1).first == isl[j].at(idx2).first)
                    {
                        int tmp1 = min(isl[i].at(idx1).second, isl[j].at(idx2).second);
                        int tmp2 = max(isl[i].at(idx1).second, isl[j].at(idx2).second);
                        int tmp_r = isl[i].at(idx1).first;
                        for (int idx3 = tmp1 + 1; idx3 < tmp2; idx3++) {
                            if (map[tmp_r][idx3] != 0) {
                                con_check = 1;
                                break;
                            }
                        }
 
                        if (con_check == 1)
                            continue;
 
                        int dis = abs(tmp1 - tmp2);
                        if (dis == 2)
                            continue;
 
                        if (result == 0) {
                            result = dis;
                        }
                        else {
                            result = min(result, dis);
                        }
                    }
                }
            }
            result -= 1;
            if (result > 1) {
                check[i][j] = result;
                i_v.push_back(item(i, j, check[i][j]));
            }
        }
    }
 
    // Make Bridge
    comb(1, 0);
 
    cout << answer << endl;
    return 0;
}