[ 백준 16137 ] 견우와 직녀 (C++)

백준의 견우와직녀(16137) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 문제를 확실하게 해보자. (문제를 확실하게 이해하신분은 2)번으로 !)

   사실 본인이 문제를 이해하지 못해서 제대로 푸는데 오래걸렸다....

   먼저 입력으로 주어지는 변수값들과 입력받는 맵의 숫자들의 의미부터 정확하게 알고가자.

   - N = 맵의 크기

   - M = 오작교의 주기

     → M의 배수시간에만 오작교를 생성가능.
     → 만약, M의 값이 5라면, 0초, 5초, 10초, 15초... 이런식으로 생성 가능
    → 처음에 만드는 시간은 상관이 없다. 예를 들어서, 오작교를 한번도 안만들었는데, 현재시간 1초이고 오작교를 만들어야 된다

      그럼 1초 , 6초, 11초에 오작교를 만들 수 있는 게 아니라, 무조건 0초 5초 10초에만 만들 수 있다 !

   - 맵에서의 0 = 절벽

   - 맵에서의 1 = 일반 땅

   - 맵에서의 2이상의 수 = 2 이상의 숫자 오작교를 만들 수 있는 지형. 그 숫자를 주기로 만들 수 있다.

     → 쉽게 이해하려면 '특별한 오작교'라고 생각을 하자. M값이 관계없이, 맵에 입력된 그 숫자를 주기로 갖는 오작교를 만들 수

        있다는 의미이다. (만약 맵에서 6이라는 숫자가 있다면, 0초, 6초, 12초, 18초... 에 오작교 생성 가능한 지형)
     → 2이상의 숫자로 표현된 곳도 엄연히 절벽이다 ! 오작교를 만들어야 하는 지형이므로 절벽으로 판단하는게 맞다 !

   그렇다면 문제에서 하는 말을 토대로 문제의 조건들을 알아보자.

   1. "까마귀와 가치는 조금이라도 견우를 더 도와주기 위해서 절벽을 하나 골라 주기기 M분인 오작교를 하나 더 놓아주기

      로 했다."

   → 주기가 M인 오작교를 놓아주는데 무작정 M일 때 다 놓아줄 수 있는게 아니라, 무조건 오작교는 1개만 놓을 수 있다는

     의미이다. 무조건 오작교는 한 개만 만들 수 있다 !

   2. "만약, 오작교를 한 번 건넌 뒤에 또 다시 오작교로 이동하면, 견우가 더 이상 이동할 수 없는 순간이 올 수도 있다.

      견우는 안전을 위해 두 번 연속으로 오작교를 건너지는 않기로 했다."
   → 오작교를 두 번 연속으로는 건널 수 없다는 말이다. 이게 무슨개소리일까?? 분명 1번 조건에서 오작교는 하나만 놓아줄 수

      있다고 했는데, 하나만 놓아줄 수 있다면 절대로 두 번 연속으로 건널일이 왜 생기는걸까??

      이런 경우를 생각해보자. 맵이 1 6 0 1 1 이렇게 생긴 맵을 생각해보자.

      먼저 6에서 '특별한 오작교'를 하나 건너게 될 것이다. 그렇다면 여기서, 우리는 1번의 조건에 맞게 절벽을 하나 골라

      오작교를 만든 것일까? 아니다. 1번 조건에서 말한 오작교는 주기가 M인 일반적인 오작교를 의미한다.

      6은 특별한 오작교 이기 때문에, 1번조건에 의하면, 아직 우리는 주기가 M인 오작교를 한 개도 놓지 않은 상황이다.

      그렇다면 6에서 특별한 오작교로 건넜다고 생각해보자. 그 다음에 바로 0이 나와버린다. 그렇다면 우리는 아직 주기가

      M인 오작교를 안만들었으니까 여기서 만들면되네? 가 안된다는 말이다. "두 번 연속으로 오작교를 건너지는 않겠다!"

      가 이 말을 의미하는 것이다.

2) 이제 문제를 제대로 이해했으니 문제풀이로 들어가보자. 본인은 BFS알고리즘을 이용해서 완전탐색하는 방법을 이용해보았다.

   BFS로 완전탐색을 하기 전, 오작교를 만들 수 없는 지형들을 맵에서 -1로 바꿔주었다.

   바꿔주는 방법은, 0으로 입력받은 모든 좌표에서 가로 양쪽(왼쪽, 오른쪽) 좌표들을 확인했을 때, 그 좌표값이

   0 이거나 -1 이거나 2이상이면 가로절벽의갯수++

   세로 양쪽(위쪽, 아래쪽) 좌표들을 확인했을 때, 그 좌표값이 0이거나 -1이거나 2이상이면 세로절벽의갯수++

   이렇게 주변에 있는 절벽의 갯수들을 Count해준 후, 가로 절벽의 갯수가 1개 이상이고, 세로 절벽의 갯수가 1개 이상이면

   절벽이 교차하는 곳이기 때문에 절벽이면서 오작교를 만들 수 없는 좌표라는 의미로 -1로 바꿔주었다.

   (본문함수 : Check_Cliff_State()) 아 그리고 ! 위에서 말했듯이, 2이상의 좌표값들은 절벽이라고 보는게 맞다 !

3) BFS를 이용해서 완전탐색하는 방법에 대해서 알아보자. 먼저 본인은 BFS탐색에 사용될 Queue에서 4개의 값을 관리해 주었다.

   (x좌표(int), y좌표(int), 주기가 M인 오작교를 만들었는지(bool), 이 전에 오작교를 건너왔는지(bool))

   주기가 M인 오작교를 만들었는지 판단하는 것은 오로지 오작교를 1개만 놓을 수 있기 때문에, 주기가 M인 오작교를 만드는

   순간, true의 값을 가지게된다. 또한, 이전에 오작교를 건너왔는지에 대한 변수가 필요한 이유는 위에서 말했듯이

   두 번 연속해서 오작교를 건널 수는 없기 때문에 이 전에 오작교를 건너왔다면 true의값을 그게 아니라면 false의 값을 가지도록

   설정해주었다.

   문제에서 구하고자 하는것은 (0, 0)에서 (N-1, M-1)까지 가는데 걸리는 시간이다. 본인은 이 시간을 저장하기 위해서

   Dist[][][2] 3차원 배열을 사용해주었다.

   Dist[a][b][0] = c 의 의미는 "다리를 만들지 않고, (a, b)까지 오는데 걸리는 시간은 c초입니다." 를 의미하고

   Dist[a][b][1] = c 의 의미는 "다리를 만들고, (a, b )까지 오는데 걸리는 시간은 c초입니다." 를 의미한다.

   이렇게 설정해준 이유는 같은 좌표라도, 다리를 만들고 왔냐 안만들고 왔냐에 따라서 걸리는 시간이 달라질 수 있기 때문에

   기존에 방문한 좌표보다 더 오랜시간에 걸려서 해당 좌표에 도착하더라도, 다리를 만들고 오는경우와 안만들고 오는 경우는

   다른 경우이기 때문이다.

   BFS탐색 조건을 알아보자.

   이동하려는 좌표값이 -1이면 ? continue ! 탐색할 수가 없는 좌표이다.

   이동하려는 좌표값이 1이면 ? 일반 땅을 의미하므로, 그대로 진행하고 걸린 시간 갱신.

   이동하려는 좌표값이 0이면 ?

   0이라는 것은 오작교를 만들어야 하는 절벽이라는 것을 의미한다.

   즉, "이전좌표에서 다리를 만들었는지?(두번연속 오작교 생성 불가능)" , "지금까지 다리를 한번도 안만들었는지?(오작교는

   단 한개만 생성)" 에 대해서 조건을 만족할 때 시간을 갱신 후 다리를 만들어 주면 된다.

   이를 위해서, 우리는 queue에서 관리하는 변수에, bool형 자료형 2개를 넣어준 것이다.

   또한, 시간을 갱신하는 부분은 소스코드를 참고하도록 하자. (본문함수 : Set_Time())

   이동하려는 좌표값이 2라면 ?

   특별한 오작교를 만들 수 있는 좌표라는 말인데, 못만드는 경우가 한 가지 있다.

   바로 이전에 오작교를 만들고 왔다면 못만든다. 즉 1 0 6 1 1 과 같은 경우 6에서는 오작교를 만들 수가 없다. 왜냐하면

   오작교는 두번 연속해서 만들 수 없기 때문이다 !

   각 조건에 맞게, Queue의 값을 적절하게 바꿔주면서 완전탐색을 진행해주면 된다.

   또한, Dist[][][]의 초기값은 무한대로 설정해주었다. 계속해서 더 작은 값으로 시간을 갱신해줘야 하기 때문이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
int Dist[MAX][MAX][2];
 
vector<pair<int, int>> Cliff;
 
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 Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 0)
            {
                Cliff.push_back(make_pair(i, j));
            }
            Dist[i][j][0] = 987654321;
            Dist[i][j][1] = 987654321;
        }
    }
}
 
void Check_Cliff_State()
{
    for (int i = 0; i < Cliff.size(); i++)
    {
        int x = Cliff[i].first;
        int y = Cliff[i].second;
 
        int Garo_Cliff_Cnt = 0;
        for (int j = 0; j < 2; 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] == -1 || MAP[nx][ny] >= 2 ) Garo_Cliff_Cnt++;
            }
        }
 
        int Sero_Cliff_Cnt = 0;
        for (int j = 2; 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] == -1 || MAP[nx][ny] >= 2) Sero_Cliff_Cnt++;
            }
        }
 
        if (Garo_Cliff_Cnt >= 1 && Sero_Cliff_Cnt >= 1) MAP[x][y] = -1;
    }
}
 
int Set_Time(int Cur_Time, int Period)
{
    int R_Value = Cur_Time;
    while (1)
    {
        if (R_Value % Period == 0) break;
        R_Value++;
    }
    return R_Value;
}
 
void BFS(int a, int b)
{
    queue<pair<pair<int, int>, pair<bool, bool>>>Q;
    Q.push(make_pair(make_pair(a, b), make_pair(false, false)));
    Dist[a][b][0] = 0;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        bool Bridge = Q.front().second.first;
        bool Before_State = Q.front().second.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 (MAP[nx][ny] == -1) continue;
 
                if (MAP[nx][ny] == 1)
                {
                    if (Dist[nx][ny][Bridge] > Dist[x][y][Bridge] + 1)
                    {
                        Dist[nx][ny][Bridge] = Dist[x][y][Bridge] + 1;
                        Q.push(make_pair(make_pair(nx, ny), make_pair(Bridge, false)));
                    }
                }
                else if (MAP[nx][ny] == 0)
                {
                    if (Bridge == false && Before_State == false)
                    {
                        int Temp_Time = Set_Time(Dist[x][y][Bridge] + 1, M);
                        if (Dist[nx][ny][1] > Temp_Time)
                        {
                            Dist[nx][ny][1] = Temp_Time;
                            Q.push(make_pair(make_pair(nx, ny), make_pair(true, true)));
                        }
                    }
                }
                else if (MAP[nx][ny] >= 2)
                {
                    if (Before_State == false)
                    {
                        int Temp_Time = Set_Time(Dist[x][y][Bridge] + 1, MAP[nx][ny]);
                        if (Dist[nx][ny][Bridge] > Temp_Time)
                        {
                            Dist[nx][ny][Bridge] = Temp_Time;
                            Q.push(make_pair(make_pair(nx, ny), make_pair(Bridge, true)));
                        }
                    }
                }
            }
        }
    }
}
 
void Solution()
{
    Check_Cliff_State();
    BFS(0, 0);
    cout << Min(Dist[N - 1][N - 1][0], Dist[N - 1][N - 1][1]) << 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;
}
// 오작교를 연속으로 놓을 수 없다.
// 다리를 하나만 놓을 수 있다.