[ 백준 1261 ] 알고스팟 (C++)

)

백준 알고스팟(1261) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 다익스트라 알고리즘으로 접근하면 쉽게 풀 수 있는 문제이다.

   문제에 사용되는 맵은 총 2개가 있다.

   입력을 받아 저장하는 MAP[][] 2차원 배열과, 경로를 계산하는 Dist[][] 2차원 배열이다.

   Dist[][] 2차원 배열은 초기에 모두 무한대의 값으로 초기화를 설정해놓았다.

   경로라고 설명했는데, 이 문제에 입각해서 더욱 구체적으로 설명하자면 (x, y)에 오는데 문을 부순 갯수이다.

   Dist[a][b] = 1 이라는 값이 있다면, (a, b)에 오는데 1개의 문을 부셨습니다 를 의미한다.

 

2. 전체적인 풀이에 대해서 알아보자.

   한 정점을 기준으로 상하좌우를 탐색하는데, 탐색한 정점의 문을 부순 갯수와 현재 문을 부순 갯수에 대해서 비교를

   하는 것이다.

   예를 들어서 설명해보겠다.

  우리가 입력받은 맵이 이러한 모양이라고 생각해보자.

   위의 설명대로 Dist[][]의 값은

  이러한 상태일 것이다. (0,0)에서 시작하므로 (0,0)만 0의 값을 가지고

   나머지 정점들은 무한대의 값을 가질 것이다.

   여기서 (0, 1)을 가는 방법에 대해서 생각해보자.

   총 3가지의 방법이 있을 것이다.

   방법 1 : (0, 0) → (0, 1)

   방법 2 : (0, 0) → (1, 0) → (1, 1) → (0, 1)

   방법 3 : (0, 0) → (1, 0) → (1, 1) → (1, 2) → (0, 2) → (0, 1)

   방법 1을 통해서 간다면 문을 부순 횟수는 0.

   방법 2를 통해서 간다면 문을 부순 횟수는 2.

   방법 3을 통해서 간다면 문을 부순 횟수는 3. 이 될 것이다.

   그렇다면, 이 값들을 통해서 구체적으로 비교해보자.

   우리가 탐색하려는 정점이 문이냐 아니냐에 따라서 구분을 해야 한다.

   if(MAP[nx][ny] == 1) or if(MAP[nx][ny] == 0) 이렇게 2가지에 대해서 !

   문이면 어떻게 해야 할까? 현재까지 부셨던 문의 갯수 + 1을 한 값이 저장이 될 것이다.

   문이 아니라면? 현재까지 부셨던 문의 갯수가 저장이 될 것이다.

  

   방법 1의 경로를 위의 설명과 합쳐서 생각해보자.

   (x, y) = (0, 0) , (nx, ny) = (0, 1)

   Dist[x][y] = 0 , Dist[nx][ny] = Min(Dist[nx][ny], Dist[x][y])

   이렇게 될 것이다. 그렇게되면 (0, 1)의 값도 0이 될 것이다. 이 말이 의미하는 것은 (0, 1)에 오는데 필요한 문을 부순 횟수는

   0개 입니다 가 될 것이다.

   이 상태에서 방법2와 방법3을 통해서 (0, 1)에 접근하게 된다면

   이미 설정되어 있는 0 이라는 값과 비교하게 될 것이며, 더 작은 횟수는 0이므로 (0, 1)의 최종값은 0이 될 것이다.

   이런식으로 비교를 하고, (M-1, N-1)의 값을 출력한다면 결과를 얻을 수 있을 것이다.

[ 소스코드 ]

 

#include<iostream>
#include<string>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
int Dist[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    Answer = 987654321;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        string Inp;
        cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            MAP[i][j] = Inp[j] - '0';
            Dist[i][j] = 987654321;
        }
    }
}
 
void Print()
{
    cout << "#############################" << endl;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << Dist[i][j] << " ";
        }
        cout << endl;
    }
    cout << "#############################" << endl;
 
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Dist[a][b] = 0;
 
    while (Q.empty() == 0)
    {
        //Print();
        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 >= M || ny >= N) continue;
            
            if (MAP[nx][ny] == 1)
            {
                if (Dist[nx][ny] > Dist[x][y] + 1)
                {
                    Dist[nx][ny] = Dist[x][y] + 1;
                    Q.push(make_pair(nx, ny));
                }
            }
            else if (MAP[nx][ny] == 0)
            {
                if (Dist[nx][ny] > Dist[x][y])
                {
                    Dist[nx][ny] = Dist[x][y];
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Solution()
{
    BFS(0, 0);
    cout << Dist[M-1][N-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;
}