[ 백준 2931 ] 가스관 (C++)

백준의 가스관(2931) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는, 가스가 흐르는 방향을 생각해서, 도둑이 훔쳐간 빈 가스관 자리를 다시 채워넣어야 하는 문제이다.

   여기서, 우리는 문제를 제대로 이해해야 될 필요가 있다. 문제에서 원하는 것이 M에서 Z까지 가스가 흐르는 것을 원하는 건

   지 아니면, 모든 가스관을 다 사용하는 것을 원하는 건지를 파악해야 한다.

   정답은 모든 가스관을 다 사용하는 것을 원하는 것이다. 실제로 문제에 예제입력2 번으로 주어진 입력을 잘 보면, 없어진 가

   스관 을 채워넣지 않아도, M에서 Z까지 모두 흐를수가 있다. 즉, 우리는 M에서 Z까지 가스를 흐르게 하는 것이 목적이 아닌,

   모든 가스관에 가스가 흐르게 만들어 줘야 한다.

   ( 사실 본인은 처음에는 M 에서 Z까지만 가스가 흐르면 된다고 생각하고 구현해서 많은 시간을 날려먹었다.. )

  

   먼저, 문제를 풀기전에 우리가 항상 기억해야 될 것이 있다. 바로 '가스가 흐르는 방향' 이다. 가스관마다 가스가 유입되는

   방향에 따라서, 나가는 방향이 결정되어 진다. 즉, 우리는 푸는 내내 가스가 흐르는 방향에 대해서 관리해줄 필요가 있다.

   간단하게 가스가 흐르는 방향을 관리해주는 함수부터 한번 보고 다음단계를 진행해보자.

  

   본인은 0,1,2,3 순서대로 동서남북의 방향을 의미하도록 코드를 구현했다.

   가스관의 모양마다, 유입될 수 있는 가스의 방향이 있고 유입이 될 수 없는 방향이 있다.

   예를 들어서 '|' 이 모양의 가스관의 경우, 동쪽이나 서쪽에서는 가스가 절대로 유입될 수 없다. 이러한 경우처럼 가스가 유입될

   수 없는 방향으로 가스관에 가스가 유입되려고 할 때, -1의 값을 return해 주도록, 그게 아니라면 정상적으로 가스가 흘러 나갈 수

   있는 방향을 return해주는 함수를 구현하였다.

   그렇다면 이제 문제를 푸는 큰 틀을 알아보고 순차적으로 구체적으로 구현하는 방법을 알아보자.

   1. 'M'에서 시작해서 탐색을 하면서, 도둑당한 빈 곳을 찾아내기.

   2. 빈 곳에 7개의 가스관을 모두 넣어보고, 가스가 제대로 흐르는지 + 모든 가스관에 가스가 흐를 수 있는지 판단.

   3. 2번조건이 맞다면 종료.

2) 단계적으로 구체적인 구현 내용을 알아보자. 먼저, 우리는 탐색을 하면서 빈 곳을 찾아내야 한다.

   즉, BFS에서 가스관이 있는 방향으로 가스가 흐르면서 빈곳을 찾아내야 한다.

   이 때, 시작점이 M이냐 아니냐에 따라서 달라진다.

   'M'일 경우 우리가 탐색을 시작하는 최초 탐색좌표로써, 상하좌우에 어디에 가스관이 존재하는지 알아 내야 한다.

   심지어는, M주변에 바로 도둑당한 빈 곳이 존재할 수도 있으며, M 바로 옆에 Z가 존재할 수도 있다.

   따라서, 본인은 BFS함수를 구현하는데, Queue에 push된 좌표가 M의 좌표인가 아닌가에 따라서 따로 구현해주었다.

   [ M일 경우 ]

   크게 2가지 경우로 나뉜다. M옆에 존재하던 가스관이 도둑맞아서, M을 기준으로 동서남북으로 모두 '.'만 존재할 경우와

   그게 아닌, 가스관이 동서남북 중 한 곳에라도 존재하는 경우로 

   1. 먼저, 가스관이 동서남북 중 한 곳에라도 존재하는 경우는 어떻게 해야 할까??

     이 경우에는, 가스관의 모양을 파악하고, 가스가 흐르는 방향을 설정해주고, Queue에 push하면서 탐색을 계속하면 된다.

     즉, 빈 곳을 찾을 때 까지 계속 진행해줘야 한다.

   2. 만약에 M주변에 가스관이 하나도 없는 경우는 어떻게 해야할까??

     먼저, 어떻게 할지는 둘째 치고, M주변에 가스관이 하나도 없음을 어떻게 판단해줘야할까?? 본인은 Queue의 Size를 이용해서

     판단해 주었다. 만약, M주변에 하나의 가스관이라도 있었다면, 그 가스관이 있는 좌표를 Queue에 넣고 진행이 계속 되었을

     것이다. 하지만, 가스관이 하나도 없는 경우, Queue의 Size는 0일 것이다.

     즉, M을 기준으로 동서남북을 모두 탐색했는데, Queue의 Size가 0일 경우 동서남북 4방향에, 7가지 파이프의 모양을

     모두 넣어서 가스가 제대로 흐르는지 판단해줘야 한다.

    

     본인은, BFS함수의 return형을 pair<int, int> 로 설정해주었다. 빈 공간을 찾든, 'Z'에 도착하든, 해당 좌표를 받아오는 것이

     필요하기 때문이다. 'Z'에 도착하게 되면, { -1, -1 }을 return 하게 해주었으며, 이 경우에도 그대로 코드를 끝내는 것이

     아닌 모든 파이프가 사용되었는지 확인해 줘야 한다.

     [ M이 아닐 경우 ]

     1. M일 아닌 경우에는, 가스가 흐르는 방향에 있는 다음 좌표만 탐색을 계속 하면 된다. 탐색을 계속 진행하다가,

       가스가 흘러야 하는 방향인데, 빈 곳이라면 그 빈 곳이 도둑당한 좌표이기 때문에, 그 좌표를 return시키면 된다.

       return시킨 이후에는, 해당 좌표에 7개의 가스관을 모두 집어 넣어주고 'Z'까지 가면서, 모든 파이프에 가스가 흐르는지

       판단 후에, 정답을 도출해 주면 된다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 26
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int dir;
}Gas;
 
int R, C, Pipe_Cnt, Temp_Pipe_Cnt;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
char Pipe[] = { '|', '-', '+', '1', '2', '3', '4' };
bool Pipe_Num[8];
 
pair<int, int> Start, End;
vector<pair<int, int>> Pipe_Pos;
 
void Input()
{
    cin >> R >> C;
    for (int i = 1; i <= R; i++)
    {
        for (int j = 1; j <= C; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'M')
            {
                Start.first = i;
                Start.second = j;
            }
 
            if (MAP[i][j] != 'M' && MAP[i][j] != 'Z' && MAP[i][j] != '.')
            {
                Pipe_Pos.push_back(make_pair(i, j));
            }
        }
    }
}
 
int Set_Direct(int dir, char C)
{
    int nd = -1;
    if (C == '|')
    {
        if (dir == 2 || dir == 3) nd = dir;
    }
    else if (C == '-')
    {
        if (dir == 0 || dir == 1) nd = dir;
    }
    else if (C == '+') nd = dir;
    else if (C == '1')
    {
        if (dir == 3) nd = 0;
        else if (dir == 1) nd = 2;
    }
    else if (C == '2')
    {
        if (dir == 2) nd = 0;
        else if (dir == 1) nd = 3;
    }
    else if (C == '3')
    {
        if (dir == 0) nd = 3;
        else if (dir == 2) nd = 1;
    }
    else if (C == '4')
    {
        if (dir == 0) nd = 2;
        else if (dir == 3) nd = 1;
    }
 
    return nd;
}
 
bool Can_Use_All_Pipe()
{
    for (int i = 0; i < Pipe_Pos.size(); i++)
    {
        int x = Pipe_Pos[i].first;
        int y = Pipe_Pos[i].second;
        
        if (Visit[x][y] == false) return false;
    }
    return true;
}
 
pair<int, int> BFS()
{
    queue<Gas> Q;
    Gas Start_Gas = { Start.first, Start.second, 0 };
    Q.push(Start_Gas);
 
    int nx, ny;
    bool Answer = false;
 
    while (Q.empty() == 0)
    {
        if (Answer == true) break;
        int x = Q.front().x;
        int y = Q.front().y;
        int dir = Q.front().dir;
        Q.pop();
 
        if (MAP[x][y] == 'M')
        {
            for (int i = 0; i < 4; i++)
            {
                nx = x + dx[i];
                ny = y + dy[i];
 
                if (nx >= 1 && ny >= 1 && nx <= R && ny <= C)
                {
                    if (MAP[nx][ny] == 'Z') continue;
                    if (MAP[nx][ny] != '.')
                    {
                        dir = Set_Direct(i, MAP[nx][ny]);
                        if (dir != -1)
                        {
                            Q.push({ nx, ny, dir });
                            if (Visit[nx][ny] == false) Visit[nx][ny] = true;
                        }
                    }
                }
            }
 
            if (Q.size() == 0)
            {
                for (int i = 0; i < 4; i++)
                {
                    memset(Visit, false, sizeof(Visit));
 
                    if (Answer == true) break;
                    nx = x + dx[i];
                    ny = y + dy[i];
 
                    if (nx >= 1 && ny >= 1 && nx <= R && ny <= C)
                    {
                        for (int j = 0; j < 7; j++)
                        {
                            memset(Visit, false, sizeof(Visit));
 
                            MAP[nx][ny] = Pipe[j];
                            pair<int, int> Temp;
                            Temp = BFS();
                            if (Temp.first == -1 && Temp.second == -1)
                            {
                                
                                if (Can_Use_All_Pipe() == true)
                                {
                                    Answer = true;
                                    cout << x << " " << y << " " << Pipe[j] << endl;
                                    exit(0);
                                }
                            }
                            MAP[nx][ny] = '.';
                        }
                    }
                }
            }
        }
        else
        {
            nx = x + dx[dir];
            ny = y + dy[dir];
 
            if (nx >= 1 && ny >= 1 && nx <= R && ny <= C)
            {
                if (MAP[nx][ny] == '.') return{ nx, ny };
                if (MAP[nx][ny] == 'Z') return{ -1, -1 };
 
                dir = Set_Direct(dir, MAP[nx][ny]);
                if (dir == -1) return { nx ,ny };
                if (Visit[nx][ny] == false) Visit[nx][ny] = true;
                Q.push({ nx, ny, dir });
            }
        }
    }
}
 
void Solution()
{
    pair<int, int> Before, After;
    Before = BFS();
    int x = Before.first;
    int y = Before.second;
    //cout << x << " , " << y << endl;
 
    for (int i = 0; i < 7; i++)
    {
        MAP[x][y] = Pipe[i];
        //cout << MAP[x][y] << "<-" << endl;
        /*for (int i = 1; i <= R; i++)
        {
            for (int j = 1; j <= C; j++)
            {
                cout << MAP[i][j] << " ";
            }
            cout << endl;
        }*/
        memset(Visit, false, sizeof(Visit));
        After = BFS();
        if (After.first == -1 && After.second == -1)
        {
            if (Can_Use_All_Pipe() == true)
            {
                cout << x << " " << y << " " << Pipe[i] << endl;
                return;
            }
        }
    }
}
 
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;
}