[ 백준 5022 ] 연결 (C++)

백준의 연결(5022) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제를 어떻게 구현할지를 생각하기 전에, 어느 경우가 문제에서 요구하는대로 전선의 길이의 최소가 되는지를 생각해보자.

   우리는 2개의 전선을 만들어주어야 하는데, 이 때 2개의 길이를 더했을 때 최소의 값을 찾아야 한다.

   그렇다면 문제에서 주어진 그림에서 한번 다른 경우를 생각해보자. 아래 그림과 같이

  

   문제에서 주어진 그림에서 전선을 문제에서 연결한것 처럼이 아닌, 위의 모양과 같이 연결했다고 생각해보자.

   그렇다면 저 전선이 경우에 따라 최소가 될 수도 있을까 ?? 절대 그럴 수가 없다.

   지금은 직관적으로 봤을 때 딱봐도 최소가 아닌 것 같아서 그렇게 생각할 수도 있지만, 정확하게 말하자면 두 전선의 길이의

   합이 최소가 되려면, 두 전선 중 하나의 길이는 무조건 최소값이여야 한다.

   그렇다면 우리는 여기서 문제를 어떻게 접근해야 할지 눈치챌 수가 있다.

   두 전선 중, 먼저 하나의 전선을 최소의 길이로 연결시켜놓고, 나머지를 연결하면 식으로 접근해 볼 수 있다.

   그런데 여기서 또 하나의 문제가 생긴다. 먼저 하나의 전선을 최소의 길이로 연결시킨다고 했는데, A랑 B중에서 무슨 전선을

   먼저 연결시켜야 할까??

   그건 우리가 알 수 없다. 즉, 이 2가지의 경우를 모두 다해봐야 한다는 것이다.

   우리가 구현해야할 내용을 정리해서 적어보면 다음과 같다.

   1. A를 먼저 최소의 길이로 연결시키고 그 전선들과 겹치지 않게 B를 연결시켰을 때의 전선의 길이 구하기.

   2. B를 먼저 최소의 길이로 연결시키고 그 전선들과 겹치지 않게 A를 연결시켰을 때의 전선의 길이 구하기.

  

2) 이제 구현하는 방법에 대해서 알아보기 전에 ! 구현에 앞서 우리가 이 문제에서 주의해줘야 할 것이 몇 가지 있다.

   첫 번째는 범위이다. 아무런 생각없이 N과 M의 최대값이 100이기 때문에, 2차원 맵을 100의 범위로 만들어서는 안된다.

   다시 1)에 있는 그림을 다시한번 봐보자. 저 그림이 N = 6, M = 6일때의 그림이다. 그런데 제일 왼쪽 상단의 점을

   (0, 0)으로 생각했을 때, 가장 오른쪽 상단의 점은 (0, 6)이 된다. 즉, 가로의 길이인 6을 입력받았다면, 우리가 보통

   풀어온 문제대로 생각했을 때, (0, 5)까지가 있는게 맞는데 (0, 6)까지가 존재한다. 즉, 가로의 길이를 100으로 입력받았다면

   (0, 100)까지가 존재할 것이다. 따라서 맵의 범위를 100이 아닌 100 + 1 로 설정해 줘야 한다는 것이다.

   두 번째는 좌표이다. (이 부분은 구현하는 사람에 따라서 헷갈리지 않게, 원래 하던 대로 주어졌다고 생각할 수 있는

   부분입니다.)

   예제 입력1을 보게 되면 A1의 위치를 (2, 1)로 주었다. 하지만, (2, 1)은 컴퓨터가 생각하는 위치는 그림에서 주어진 A1의

   위치와 다르다. 아마 밑으로 2칸 내려가고 오른쪽으로 한칸 움직인 곳의 좌표가 컴퓨터가 생각하는 위치일 것이다.

   즉, 그림에서 주어진 (2, 1)은 컴퓨터에서는 (1, 2)가 맞다. 따라서, 본인은 입력을 x와 y값을 반대로 입력받아 주었다.

 

   이제 본격적인 구현에 들어가보도록 하자. 구현의 순서는 위에서 파랑색으로 표시된 2가지 과정을 진행하면 된다.

   그렇다면 전선을 연결하는 부분에 대해서 알아보자.

   본인은 완전탐색 방법 중, BFS탐색을 통해서 전선의 최단거리를 찾아 주었다.

   BFS탐색에 사용되는 Queue에서는 본인이 직접 만든 구조체를 관리해 주었는데, 구조체에 들어가는 변수는 다음과 같다.

 typedef struct

{
    int x;

int y;

vector<pair<int,int>> Route;

}Info;

   여기서 이상한 구조체변수를 하나 볼 수 있다. 바로 Vector이다. Vector를 사용한 이유는 경로를 저장하기 위함이다.

   그렇다면 경로를 왜 저장해 주었을까?? 바로 그 다음에 연결한 다음 전선이 이 해당 경로에는 전선을 깔지 못하게 표시해

   주기 위해서 경로를 저장하는 벡터를 만들어 준 것이다.

   또한, BFS탐색에서 가장 필요한 방문표시를 해주는 Visit배열을 2개를 만들어 주었다.

   하나는 Temp_Visit, 하나는 Visit라는 이름을 갖고 있는데, Temp_Visit는 현재 연결하려는 전선이 연결하는 경로를 탐색할

   때, 중복해서 탐색하지 않게 하기 위한 (우리가 일반적으로 사용하는 Visit배열이라고 생각하면 됨 !) 배열이고,

   Visit는 A든 B든 먼저 전선을 깐 놈들이 전선을 깔았다고 표시해주는 배열이다.

  

   그리고 사실 BFS부분은 코드가 조금 더럽다(?) 라는 느낌을 받을 수 있을 것 같아서, 코드에서 주석으로

   하나하나 밑에서 설명하겠다.

   마지막으로 주의해야 할 점은 전선의 길이를 체크하는 부분이다.

  

   여기서 A전선의 길이는 6이다. 그런데 계산을 하면 7이 나올 것이다. 왜냐하면 본인은 좌표의 갯수를 Count해주었기

   때문이다. 즉, 7개의 좌표를 지나고 있기 때문에 7이 나오게 된다.

   B의 전선의 길이도 10이 나올 것이다. 왜냐하면 길이가 9인 전선에 10개의 좌표가 존재하기 때문이다.

   따라서 ! 우리는 A의 길이, B의길이를 모두 구했다면 더해서 2를 빼주면 된다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 101
using namespace std;
 
typedef struct
{
    int x;
    int y;
    vector<pair<int, int>> Route;
}Info;
 
int N, M, Answer = 999999999;
int A_Length, B_Length;
int MAP[MAX][MAX];
bool Temp_Visit[MAX][MAX];
int Visit[MAX][MAX];
bool A_Flag, B_Flag, Answer_Flag;
 
pair<int, int> A_Pos[2], B_Pos[2];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Print()
{
    cout << "###################################################" << endl;
    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            cout << Visit[i][j] << " ";
        }
        cout << endl;
    }
    cout << "###################################################" << endl;
}
 
void Input()
{
    cin >> M >> N;
 
    for (int i = 0; i < 2; i++)
    {
        int x, y; cin >> x >> y;
        A_Pos[i].first = y;
        A_Pos[i].second = x;
    }
    for (int i = 0; i < 2; i++)
    {
        int x, y; cin >> x >> y;
        B_Pos[i].first = y;
        B_Pos[i].second = x;
    }
}
 
void BFS(int a, int b, int da, int db, char c)
// BFS(시작 x좌표, 시작 y좌표, 도착 x좌표, 도착 y좌표, A를 까는지 or B를 까는지 구분)
{
    queue<Info> Q;
    // 위에서 말한대로 구조체를 자료형으로 사용하는 Queue 선언.
    vector<pair<int, int>> V;
    Info Temp;
    Temp.x = a; Temp.y = b; Temp.Route.push_back(make_pair(a, b));
    Q.push(Temp);
    // Queue에 초기값 Push
    Temp_Visit[a][b] = true;
    if (c == 'A') Visit[a][b] = 1;
    // A전선을 깔면 Visit배열을 1로 표현
    else Visit[a][b] = 2;
    // B전선을 깔면 Visit배열을 2로 표현
    // => 즉, Visit배열이 0이다 = 아무 전선도 깔려 있지 않은 곳이다 를 의미.
 
    while (Q.empty() == 0)
    {
        int x = Q.front().x;
        int y = Q.front().y;
        vector<pair<int, int>> R = Q.front().Route;
        Q.pop();
 
        if (x == da && y == db)    // 도착점에 도착한다면
        {
            if (c == 'A')        // A전선을 까는 중이였다면
            {
                A_Flag = true;    // A를 깔았다고 표시.
                for (int i = 0; i < R.size(); i++)
                {
                    int Rx = R[i].first;
                    int Ry = R[i].second;
                    Visit[Rx][Ry] = 1;
 
                    A_Length++;
                }
                // 위의 for문은 연결된 최단경로에 이미 전선을 깔았다고
                // 표시해주는 역할. 동시에 길이를 계산함.
            }
            else                // 위와 똑같은데, B전선을 까는 중이였다면 
            {
                B_Flag = true;
                for (int i = 0; i < R.size(); i++)
                {
                    int Rx = R[i].first;
                    int Ry = R[i].second;
                    Visit[Rx][Ry] = 2;
 
                    B_Length++;
                }
            }
            return;
        }
    
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            vector<pair<int, int>> nR;
 
            for (int j = 0; j < R.size(); j++) nR.push_back(R[j]);
            // 기존의 Route를 일단 다 옮겨준다.
            
            if (nx < 0 || ny < 0 || nx > N || ny > M) continue;
            // 범위Out이면 continue
            if (c == 'A')    
            {
                if ((nx == B_Pos[0].first && ny == B_Pos[0].second) || (nx == B_Pos[1].first && ny == B_Pos[1].second)) continue;
                if (Temp_Visit[nx][ny] == true || Visit[nx][ny] != 0) continue;
                // A를 까는 중일 때, B의 2점 중 한 점이 있는 곳이라면 그곳에는 전선을 깔 수 없다.
                // A를 까는 중일 때, 이미 방문했거나, 이미 B의 전선이 깔려있는 곳이라면 전선을 깔 수 없다.
 
                Temp_Visit[nx][ny] = true;
                nR.push_back(make_pair(nx, ny));
                Q.push({ nx, ny, nR });
            }
            else // 위와 마찬가지인데 B전선을 까는 경우임. 즉, 비교해야될 조건만 A로 바뀌게 되는 것 ! 
            {
                if ((nx == A_Pos[0].first && ny == A_Pos[0].second) || (nx == A_Pos[1].first && ny == A_Pos[1].second)) continue;
                if (Temp_Visit[nx][ny] == true || Visit[nx][ny] != 0) continue;
 
                Temp_Visit[nx][ny] = true;
                nR.push_back(make_pair(nx, ny));
                Q.push({ nx, ny, nR });
            }
        }        
    }    
}
 
void Solution()
{
    int x = A_Pos[0].first;
    int y = A_Pos[0].second;
    int xx = A_Pos[1].first;
    int yy = A_Pos[1].second;
    BFS(x, y, xx, yy, 'A');
 
    memset(Temp_Visit, false, sizeof(Temp_Visit));
    x = B_Pos[0].first;
    y = B_Pos[0].second;
    xx = B_Pos[1].first;
    yy = B_Pos[1].second;
    BFS(x, y, xx, yy, 'B');
    
    if (A_Flag == true && B_Flag == true)
    {
        Answer_Flag = true;
        Answer = Min(Answer, A_Length + B_Length);
    }
 
    memset(Visit, 0, sizeof(Visit));
    memset(Temp_Visit, false, sizeof(Temp_Visit));
    A_Length = B_Length = 0;
    A_Flag = false;
    B_Flag = false;
 
    x = B_Pos[0].first;
    y = B_Pos[0].second;
    xx = B_Pos[1].first;
    yy = B_Pos[1].second;
    BFS(x, y, xx, yy, 'B');
 
    memset(Temp_Visit, false, sizeof(Temp_Visit));
    x = A_Pos[0].first;
    y = A_Pos[0].second;
    xx = A_Pos[1].first;
    yy = A_Pos[1].second;
    BFS(x, y, xx, yy, 'A');
 
    if (A_Flag == true && B_Flag == true)
    {
        Answer_Flag = true;
        Answer = Min(Answer, A_Length + B_Length);
    }
}
 
void Solve()
{
    Input();
    Solution();
 
    if (Answer_Flag == false) cout << "IMPOSSIBLE" << endl;
    else cout << Answer - 2 << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}