[ 백준 2146 ] 다리만들기 (C++)

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

( 문제 바로가기 )

[ 문제풀이 ]

1. 문제가 조금 난이도 있는 것 같아 보이긴 한다. 하지만 일반적인 BFS에서 한 단계만 더 생각할 수 있다면 그리 어렵지

   않은 문제이다.

2. 문제에서 해결해야 될 부분이 많은 것 같으니 해야될 내용을 정리해보자.

   먼저, 서로 다른 대륙인지 같은 대륙인지 판단을 해야 한다. 바다를 건넌다고 무조건 다른 대륙이 아니기 때문이다.

  

    이런 경우, 대륙 가운데 바다가 있지만, 결국 하나의 대륙이기 때문에 같은 대륙인지 아닌지 확실하게 판단하는

    과정이 하나 필요할 것이다.

   두번째는, 다리를 연결하되, 서로 다른 대륙과 연결하는 다리를 연결해야 하며, 그 다리의 최소값을 구하는 과정이

   있어야 한다.

   그럼 우리가 해야할 일을 간단하게 요약해보자면...

   1. 대륙간의 번호 붙이기

   2. 다리 연결하기

  

3. 순서대로 해결해보자.

   대륙간의 번호를 붙여보자. 나는 이 과정을 위해서 처음 입력받을 때 육지를 1이 아닌 -1로 표현하였다.

   왜냐하면, 1,2,3... 이런 식으로 번호를 붙일 것이기 때문이다.

   모든 대륙에서 BFS의 역할을 하는 함수를 호출해주면 된다.(본문의 함수 : Make_LandLabel())

   저 함수 안에서는, Queue를 이용해서, 서로 인접해있으면서 아직 방문하지 않은 정점들의 번호를 넣어주면서

   맵에서의 값을 모두 동일한 값으로 넣어주는 반복만 해주면 된다.

4. 다리 연결하기에서는 (본문의 함수 : BFS()) 먼저 BFS를 실행하기 전, 하나의 과정을 추가해주었다.

   같은 대륙에 있는 모든 땅들을 Queue에 넣고 시작하였다.

   이후, BFS-Leveling Skill을 통해서 Queue의 Size만큼 진행을 하게 되는데,

   이 때 생각해야할 조건으로는

   1. 맵의 범위내에 존재해야 한다.

   2. 만약 이동하려는 칸이 바다라면 Queue에 넣어주고 계속 진행.

   3. 만약 이동하려는 칸이 육지이고, 이동하기 전의 대륙의 번호와 다른 번호라면 종료

   이 3가지 조건에 대해서만 구현을 해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<int, int>> V;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    Answer = 987654321;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 1)
            {
                MAP[i][j] = -1;
                V.push_back(make_pair(i, j));
            }
        }
    }
}
 
void Make_LandLabel(int a, int b, int L)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
    MAP[a][b] = L;
 
    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 < N)
            {
                if (Visit[nx][ny] == false && MAP[nx][ny] == -1)
                {
                    Visit[nx][ny] = true;
                    MAP[nx][ny] = L;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
int BFS(int Num)
{
    int Result = 0;
    queue<pair<int, int>> Q;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == Num)
            {
                Visit[i][j] = true;
                Q.push(make_pair(i, j));
            }
        }
    }
 
    while (Q.empty() == 0)
    {
        int S = Q.size();
        for (int i = 0; i < S; i++)
        {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();
 
            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 < N)
                {
                    if (MAP[nx][ny] != 0 && MAP[nx][ny] != Num) return Result;
                    else if (MAP[nx][ny] == 0 && Visit[nx][ny] == false)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                    }
                }
            }
        }
        Result++;
    }
}
 
void Solution()
{
    int Land_Label = 1;
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
 
        if (Visit[x][y] == false)
        {
            Make_LandLabel(x, y, Land_Label);
            Land_Label++;
        }
    }
 
    for (int i = 1; i < Land_Label; i++)
    {
        Answer = Min(Answer, BFS(i));
        memset(Visit, false, sizeof(Visit));
    }
    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;
}