[ 백준 1175 ] 배달 (C++)

백준의 배달(1175) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 단순해 보이는 문제였지만, 생각보다 많이 틀렸던 문제이다. 문제에서 제시하는 조건들 부터 다시한번 체크해보고 가자.

   1. 민식이는 'C'로 표현된 선물을 배달해야 하는 곳(2곳) 에 모두 방문을 해야한다.

   2. 민식이는 매 시간마다 방향을 바꿔야 한다.

  

   본인은 너비우선탐색(BFS) 방법을 이용해서 접근해 보았는데,

   처음에 본인이 많이 헷갈렸던 부분은 'C'로 표현된 2곳을 어떻게 구분하냐였다.

   BFS탐색을 할 때 가장 중요한 것이 방문처리 인데 이 문제 같은 경우 방문한 곳이더라도 또 방문해야 하는 경우가

   반드시 존재하는 문제이다.

   예를 들어서 이런 예를 한번 생각해보자.

   2 x 2 짜리 맵에서

   S C

   C #

   이렇게 맵이 있다면 어떤 'C'를 먼저 방문하던 간에, 'S'를 중복적으로 방문을 해줘야 한다.

   그렇다고 방문 체크를 안해줘 버리면 ? 아마 너무나도 많은 시간이 걸리게 될 것이고 당연히 시간초과가 발생하게 될

   것 이다.

   그래서 'C'를 들렸는지 안들렸는지로 방문체크를 한번 해보려고 했으나, 'C'가 2개다 보니까 중간중간 꼬이거나

   원하는대로 값이 제대로 들어가지 않는 경우가 발생하였다.

   그래서 본인은 편하게 하나의 'C'를 'D'로 바꿔버렸다.

   즉, 맵에는 'S' 1개, 'C' 1개, 'D' 1개가 존재하도록 바꿔버렸다.

   이 후, C를 방문했는지 안했는지, D를 방문했는지 안했는지에 따라서 같은 좌표더라도 중복적으로 탐색할 수 있도록

   구현해 주었다.

   조금 더 구체적으로 말하자면 Visit배열을 5차원 배열로 만들어 보았다.

   Visit[50][50][4][2][2] 이렇게 만들어 주었다.

   첫번째와 두번째 인덱스인 '50'이 의미하는 것은 맵의 (x, y)좌표를 의미하고, 가운데 '4'는 접근한 방향(동/서/남/북),

   가장 마지막 인덱스 2개인 '2'가 의미하는 것은 하나는 'C'를 방문했는지 안했는지, 또 하나는 'D'를 방문했는지

   안했는지로 계산을 해 보았다.

   접근한 방향까지 넣어준 이유는, BFS 탐색을 하다보면 같은 좌표를 여러번 탐색하게 된다.

   물론 방문체크 배열을 통해서 막아줄 수 있지만, 이 문제 같은 경우 같은 방향으로 연속적으로 움직일 수 없다는

   조건 때문에, 같은 좌표, 같은 상태이더라도 해당 좌표에 접근한 방향이 다르면 기존과 다른 방문이라 판단하여

   처리해 주었다. 실제로, 이부분을 넣지 않았더니 틀렸다는 결과를 얻게 되었다.

   즉, 예를 들어서 Visit[0][0][0][1][0] = true 가 의미하는 것은, (0, 0)에 0번 방향(본인 코드 기준 동쪽)으로 진입하는데

   C는 방문했고, D는 아직 방문하지 않은 상태입니다. 를 의미한다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<queue>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
struct INFO
{
    int x;
    int y;
    int Cnt;
    int Dir;
    bool C_Visit;
    bool D_Visit;
};
 
int N, M, Answer;
char MAP[MAX][MAX];
bool Visit[MAX][MAX][5][2][2];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
pair<int, int> Start;
 
void Input()
{
    int Idx = 0;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string Inp; cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            MAP[i][j] = Inp[j];
            if (MAP[i][j] == 'S')
            {
                Start.first = i;
                Start.second = j;
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == 'C')
            {
                Idx++;
                if (Idx == 2) MAP[i][j] = 'D';
            }
        }
    }
}
 
void Solution()
{
    //for (int i = 0; i < N; i++)
    //{
    //    for (int j = 0; j < M; j++)
    //    {
    //        cout << MAP[i][j] << " ";
    //    }
    //    cout << endl;
    //}
    queue<INFO> Q;
    Q.push({ Start.first, Start.second, 0, -1, 0, 0 });
    Visit[Start.first][Start.second][4][0][0] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().x;
        int y = Q.front().y;
        int Cnt = Q.front().Cnt;
        int Dir = Q.front().Dir;
        bool C_Visit = Q.front().C_Visit;
        bool D_Visit = Q.front().D_Visit;
        Q.pop();
 
        if (C_Visit == true && D_Visit == true)
        {
            Answer = Cnt;
            return;
        }
 
        for (int i = 0; i < 4; i++)
        {
            if (i == Dir) continue;
 
            int nx = x + dx[i];
            int ny = y + dy[i];
            bool nC_Visit = C_Visit;
            bool nD_Visit = D_Visit;
 
            if(nx >= 0 && ny >= 0 && nx < N && ny < M)
            { 
                if (Visit[nx][ny][i][C_Visit][D_Visit] == false && MAP[nx][ny] != '#')
                {
                    if (MAP[nx][ny] == 'C') nC_Visit = true;
                    if (MAP[nx][ny] == 'D') nD_Visit = true;
 
                    Visit[nx][ny][i][nC_Visit][nD_Visit] = true;
                    Q.push({ nx, ny, Cnt + 1, i, nC_Visit, nD_Visit });
                }
            }
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
 
    if (Answer == 0) cout << -1 << endl;
    else cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

cs