[ 백준 17472 ] 다리만들기2 (C++) (1)

백준의 다리만들기2(17472) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 어떻게 문제를 해결해 나갈지 부터 간략하게 알아본 후에 구체적인 구현방법을 알아보도록 하자.

   본인이 문제를 보고 가장 먼저 생각한 것은 "섬의 번호 붙여주기" 이다.

   섬의 번호를 붙인 후, 각 섬과 섬끼리의 거리를 구하는 것을 우선적으로 생각해 주었다.

   이 후, 구해놓은 거리를 조합을 통해서 답을 도출해 내는 식으로 생각해 보았다. 정말 간략하게 이정도만 알았으니

   정리 후, 구체적으로 들어가보자.

   1. 섬의 번호 붙이기

   2. 각 섬끼리의 거리 구하기

   3. 구해놓은 거리를 통해서 정답 도출하기

  

2) 먼저 "섬의 번호 붙이기" 이다.

   본인은 이 부분을 위해서 입력을 받을 때, 섬의 좌표들을 벡터에 모두 저장해 주었다.

   이 후, 벡터의 크기만큼 반복하면서 "아직 방문하지 않은 섬" 이라면 너비우선탐색(BFS)를 통해서 연결된 모든 좌표들을

   돌면서 섬의 번호를 순차적으로 붙여주었다. 

  

3) 두 번째는 "각 섬끼리의 거리 구하기" 이다.

   물론 여기서 말하는 거리는 "최소거리"를 의미한다. 본인은 이 과정을 위해서 먼저 2번인 "섬의 번호 붙이기" 단계에서

   설명하지 않은 한 가지를 더 진행해 주었다.

   바로 "각 섬의 좌표들을 벡터배열에 저장" 하는 것이다.

   이게 위에서 말한 입력받을 때 저장한 것과는 다른 것이다. 아래의 그림을 예시로 알아보자.

  

   위의 그림은 원본맵을, 오른쪽 그림은 원본맵에서 "섬의 번호를 붙인 후" 섬의 상태를 나타낸 것이다.  

   위와 같이 맵이 존재할 때, 처음에 말했던 입력받을 때 섬의 좌표들을 저장한 벡터에는 총 12개의 좌표를 저장한 것이다.

   이 후, 섬의 번호 붙이기 단계에서 사용한 벡터배열에는 다음과 같이 저장되어 있다.

   VectorArr[1] = { 1의 좌표 4개 } , VectorArr[2] = { 2의 좌표 4개 } , VectorArr[3] = { 3의 좌표 4개 }

   이런식으로 ! (본문에서는 벡터배열 변수명을 VectorArr[]로 사용하지 않았으니 헷갈리지 마세요)

   다시 돌아와서... 벡터 배열에 저런식으로 왜 저장했는지 생각해보자. 우리는 섬끼리의 최단거리를 구해야 한다.

   즉, 각 섬에서 또 다른 섬으로 가기 위한 최단거리를 구하기 위해서, 우리에게는 각 섬의 좌표들이 필요했고

   따라서 위와 같이 저장을 한 것이다.

   이 거리를 구하는 부분은 본인은 깊이우선탐색기법(DFS)를 이용해서 구현해 보았다.

   DFS의 탐색조건은 아래와 같이 설정해 주었다.

   1. 시작 섬과 도착 섬을 정한다.

   2. 시작 섬에서 나올 수 있는 방향을 체크한 후, 그 한 방향으로만 계속 한칸 씩 전진한다.

      - 문제에서 다리는 한 방향으로만 존재할 수 있다고 했으므로 한 방향으로만 전진하게 설정해주었다.

   3. 맵의 범위를 벗어나거나, 도착섬이 아닌 섬을 도착하는 경우 return.

   4. 도착 섬에 제대로 도착하는 경우, 거리를 비교 후 최소거리로 갱신 후 return.

  

4) 이제 각 섬들간의 거리까지 구했으니 이제 마지막으로 다리의 최소길이를 구해보자.

   먼저 본인은 위에서 구한 다리의 최단거리들을 모두 Vector에 저장해 주었다.

   (벡터가 많이 등장합니다. 본문에 주석을 참고하셔서 헷갈리시지 않게 조심하세요.)

   최단거리를 관리하는 벡터에서는 3개의 int형 변수를 관리해 주었다. { int a, int b, int c } 이런식으로 vector에

   저장되어 있는데 의미는 "a섬과 b섬의 최단거리는 c입니다." 이다.

   이 후, 본인은 조합을 구현하였다. 갑자기 무슨 ? 왜 ? 조합일까 ??

   위에서 각 섬들을 이을 수 있는 다리의 최단거리를 Vector에 저장해 주었고, 이 Vector의 원소들 중에서

   특정 원소들 몇개만 뽑아낸다면 정답을 도출할 수 있을 거라 생각하였다.

   그렇다면 몇개를 뽑아내야 될까 ?? 그걸 알 수가 없다. 그렇다고 갯수가 최소라고 최단거리일까? 그것도 아니다.

   다리가 2개로 모든 섬을 연결할 수 있고, 이 2개의 다리길이의 합이 100이고, 다리 10개로 모든 섬을 연결할 수 있고

   이 10개의 다리길이의 합이 10이라면 답은 후자가 될 것이다. 다리의 최소갯수가 아닌 최소거리를 구해야 하기 때문이다.

   그래서 본인은 조합에서 종료조건을 "1개 이상만 뽑는다면" 으로 설정해 주었다.

   이전 글인 '게리멘더링(14741)' 문제에서도 굉장히 비슷한 방법을 사용해서 풀이하였는데 이 문제에서도 똑같은

   방법을 사용해 주었다.

   섬끼리 모두 연결되기 위해서는 최소 1개 이상의 다리는 필요하기 때문에 1개 이상만 뽑으면 그 다리로 인해 모든 섬이

   연결될 수 있는지를 체크해 주었다.

  

   그렇다면 모든 섬에 연결될 수 있다는 것은 어떻게 알 수 있을까 ??

   어떤 섬에서 출발하더라도 탐색할 수 있는 섬의 최종적인 갯수가 이전에 구해놓은 섬의 갯수와 일치하면 모두 연결되었

   다고 판단할 수 있다.

   예를 들어서 섬이 총 4개가 존재한다고 생각해보자. 그리고 우리는 탐색을 1번섬에서 부터 한다고 생각해보자.

   1번섬에서 탐색을 시작했을 때, 최종적으로 탐색한 섬의 갯수가 4개라면 이것은 모두 연결되어 있음을 뜻하게 된다.

   물론 이렇게 탐색을 하기 위해서는, 우리가 뽑은 다리에 대해서는 확실하게 연결관계를 체크해 주어야 한다.

   이 부분 때문에 Vector에 3개의 변수를 넣어준 것이다. 다리의 길이와, 그 다리가 연결하는 2개의 섬을 이러한 과정

   에서 쉽게 알아낼 수 있게 !

   본인은 이렇게 탐색하는 부분을 BFS를 통해서 구현해 주었다. 1번 섬에서 출발해서, 탐색할 수 있는 섬의 갯수가

   전체 섬의 갯수와 동일하다면 정답을 최소값을 갱신, 그게 아니라면 또 다른 조합 탐색 !

   이 부분을 간단하게 정리해보자면....

   1. 조합을 통해서 다리를 하나씩 뽑는다.

   2. 1개 이상 뽑았다면, 그 뽑은 다리들이 연결하는 섬들의 연결관계를 표시해준다.

   3. 표시한 연결관계들을 기반으로, BFS탐색으로 최종적으로 탐색할 수 있는 섬의 갯수를 판단한다.

   4. 판단된 섬의 갯수가 전체 섬의 갯수와 일치하면 최소값 갱신, 그게 아니라면 또 다른 조합 추출

  

   문제의 풀이는 위와 같은데 생각보다 구현할 게 조금 있었던 편이였던 것 같다.

   마지막 부분을 완전탐색 방법으로 풀이를 하면 위와 같이 풀이할 수 있지만, 다음 글에서는 최소스패닝트리로

   구하는 법에 대해서 설명하고자 한다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 10
#define ISLAND_MAX 6 + 1
#define INF 1000
using namespace std;
 
int N, M, Area_Num, Answer = INF;
int MAP[MAX][MAX];                    // 입력 받을 맵
int Label[MAX][MAX];                // 각 섬마다 번호를 붙이기 위해 사용한 맵
int Dist[ISLAND_MAX][ISLAND_MAX];    // 각 섬의 최단거리를 저장하기 위한 배열. 
                                    // Dist[a][b] = C : a와 b의 최단거리는 c입니다.
 
bool Visit[MAX][MAX];                    // BFS탐색 시, 방문체크를 위한 배열(섬의 번호 붙일 때 사용)
bool Connect[ISLAND_MAX][ISLAND_MAX];    // 연결관계 체크를 위한 배열
bool ConnectIsland[ISLAND_MAX];            // BFS탐색 시, 방문체크를 위한 배열(연결관계를 통해, 정답을 도출하기 위한 BFS탐색 시 사용)
bool Select[ISLAND_MAX * ISLAND_MAX];    // 조합 추출에서 중복 추출을 막기 위한 배열.
/* Select배열의 크기 : 7 * 7 
   - 섬이 N개 존재하고, 이 섬들을 연결한다고 가정했을 때
     나올 수 있는 간선의 최대 갯수는 N(N-1)/2 개 입니다
*/
 
vector<pair<int, int>> V;                      // 입력 시, 모든 섬의 좌표들을 저장하기 위한 벡터
vector<pair<int, int>> Area_Pos[MAX + 1];     // 각 섬에 존재하는 땅의 좌표들을 저장하기 위한 벡터배열
vector<pair<pair<int, int>, int>> BridgeList; // 섬과 섬을 연결하는 다리의 길이와, 그 다리가 어떤 섬을 연결하는지 저장하기 위한 벡터.
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    for (int i = 0; i < 7; i++)
    {
        for (int j = 0; j < 7; j++)
        {
            Dist[i][j] = INF;
        }
    }
    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) V.push_back(make_pair(i, j));    // 입력과 동시에, 섬의 좌표들은 모두 저장.
        }
    }
}
 
void BFS(int a, int b, int Num)
{
    /* 
       연결된 땅을 탐색하면서 번호를 붙이는 함수.
       (a, b) = 탐색을 시작할 첫 정점의 좌표.
       Num = 탐색할 땅들의 붙일 섬 번호.
    */
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
    Label[a][b] = Num;
    Area_Pos[Num].push_back(make_pair(a, b));
    /* 
       설명에서도 말했듯이, 섬의 번호를 붙이면서 동시에
       각 섬에 존재하는 땅덩어리의 좌표들을 벡터배열에 저장해준다.
       이 벡터배열은, 이 후 섬들간의 최단거리를 구하는데 사용.
    */
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        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)
            {
                if (Visit[nx][ny] == false && MAP[nx][ny] == 1)
                {
                    Visit[nx][ny] = true;
                    Label[nx][ny] = Num;
                    Q.push(make_pair(nx, ny));
                    Area_Pos[Num].push_back(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void MakeLabel()
{
    /* 
        섬의 번호를 붙이는 함수
        입력 시 저장해 놓은 Vector를 순차적으로 탐색하면서
        아직 방문하지 않은 좌표들에 대해서는 BFS 탐색 실시.
    */
    int LabelNum = 1;
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
 
        if (Visit[x][y] == false) BFS(x, y, LabelNum++);
    }
    Area_Num = LabelNum;    // 섬의 최종적인 갯수 = Area_Num - 1
}
 
void DFS(int x, int y, int dir, int B_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) DFS(nx, ny, dir, B_Size + 1, Start, End);    // 아직 바다라면 계속 탐색.
    else if (MAP[nx][ny] == 1)                    // 탐색하려는 정점이 땅이라면
    {
        if (Label[nx][ny] == End)                // 그 땅이 도착섬이라면 ?
        {
            if (B_Size > 1)                        // 다리의 길이가 2이상인지 체크
            {
                if (Dist[Start][End] > B_Size)    // 최소길이로 갱신
                {
                    Dist[Start][End] = B_Size;
                    Dist[End][Start] = B_Size;
                }
                return;
            }
        }
        else return;    // 도착점이 아닌 다른 섬이라면 return.
    }    
}
 
int Reverse(int dir)
{
    if (dir == 0) return 1;
    else if (dir == 1) return 0;
    else if (dir == 2) return 3;
    else if (dir == 3) return 2;
}
 
void MakeBridge(int Start, int End)
{
    /* 시작 섬에 존재하는 모든 땅덩어리 들에서 도착 섬까지 탐색해본다.*/
    for(int i = 0 ; i < Area_Pos[Start].size(); i++)
    {
        int x = Area_Pos[Start][i].first;
        int y = Area_Pos[Start][i].second;
    
        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)
            {
                if (MAP[nx][ny] == 0) DFS(x, y, j, 0, Start, End);
            }
        }
    }
}
 
bool CheckState()
{
    memset(Connect, false, sizeof(Connect));
    memset(ConnectIsland, false, sizeof(ConnectIsland));
    for (int i = 0; i < BridgeList.size(); i++)
    {
        if (Select[i] == true)
        {
            int x = BridgeList[i].first.first;
            int y = BridgeList[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 == Area_Num - 1)
        {
            Flag = true;
            break;
        }
 
        for (int i = 1; i < Area_Num; i++)
        {
            if (Cur == i) continue;
            if (Connect[Cur][i] == true && ConnectIsland[i] == false)
            {
                ConnectIsland[i] = true;
                Q.push(i);
                IslandCnt++;
            }
        }
    }
    return Flag;
}
 
void FindDistance()
{
    /*
    섬들간의 최단거리를 구하기 위한 함수.
    시작점과 끝점을 정한 후, DFS를 통해서 구현.
    */
    for (int i = 1; i < Area_Num; i++)
    {
        for (int j = i + 1; j < Area_Num; j++)
        {
            MakeBridge(i, j);
            if (Dist[i][j] == INF) continue;
            BridgeList.push_back(make_pair(make_pair(i, j), Dist[i][j]));
            // 다리의 최소거리를 구했으면, BridgeList 벡터에 다리가 연결하는 2개의 섬과, 그 거리 총 3개의 데이터를 저장.
        }
    }
}
 
void DistDFS(int Idx, int Cnt, int Sum)
{
    /* 조합 구현을 통해서 정답을 도출하기 위한 함수.*/
    if (Cnt >= 1)    // 1개이상만 뽑았으면 무조건 확인해본다.
    {
        if (CheckState() == true)
        {
            if (Answer > Sum) Answer = Sum;
        }
    }
 
    for (int i = Idx; i < BridgeList.size(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DistDFS(i, Cnt + 1, Sum + BridgeList[i].second);
        Select[i] = false;
    }
}
 
void Solution()
{
    MakeLabel();            // 섬의 번호 붙이기
    FindDistance();            // 섬 끼리 최단거리 구하기
    DistDFS(0, 0, 0);        // 정답 도출하기
 
    if (Answer == INF) cout << -1 << endl;
    else cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}