[ 백준 15558 ] 점프 게임 (C++)

백준의 점프게임(15558) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 세로로 긴 맵 2개가 있는데, 사람이 갈 수 있는 칸은 앞으로 한칸, 뒤로 한칸, 옆 줄에서 앞으로 +K칸을 갈 수 있을 때,

   N칸이상 움직일 수 있는지 없는지 찾아내는 문제이다. 여기서 맵은 1초에 1칸씩 없어지기 떄문에, 없어진 칸으로는

   사람이 갈 수 없다는 것을 고려해주면 어렵지 않게 풀 수 있는 문제이다.

2) 본인은 BFS에서 총 3개의 변수를 관리해 주었다. { { x좌표 , y좌표 } , 현재시간 } 을 관리해주었는데, 시간을

   관리해준 이유는 각 시간마다 없어지는 칸이 존재하기 때문이다.

   구현할 때에는, 가로로 움직일 때와 세로로 움직일 때를 따로 구현해 주어야 한다.

   왜냐하면, 같은 줄에서 좌우로 움직일 때에는, 없어진칸만 고려해주면서 앞으로가거나 뒤로가거나 해주면 되지만

   옆줄로 옮겨 갈 때에는 앞으로 +K 움직여야 하기 때문이다.

   일반적인 BFS와 같이 Visit[][] 2차원 배열을 통해서 이미 탐색한 좌표에 대해서는 중복 탐색을 하지 않도록

   구현해 주었다.

  

   이 문제에서 가장 핵심인 없어지는 칸을 어떻게 관리하는지 알아보자.

   먼저 생각을 해보면, 가로로 긴 2줄의 맵이 주어진다. 그리고 1초마다 가장 왼쪽 칸이 하나씩 사라지게 된다.

   우리는 이를 위해서 시간을 관리하는 변수를 Queue에서 같이 관리해 준다고 하였다.

   맵에서 가로를 관리하는 변수는 y축이다. 즉, y의 값이 +1 되거나 -1 되거나 +k되거나 할 때 마다 시간을 관리하는

   변수보다 항상 커야 한다는 것이다.

   쉽게 생각하면 이렇다. 일반적으로 우리는 맵의 범위내에 있는 좌표인지 탐색하기 위해서

   if(x > 0 && y > 0 && x < N && y < N) 이러한 조건문을 사용하는데, 저기서 y의 범위가

   0 ~ y ~ N이 아닌, 현재시간 ~ y ~ N 으로 설정을 둬버리면, 자연스럽게 사라진 칸은 못가게 설정이 되는 것이다.

[ 소스코드 ]

 

#include<iostream>
#include<string>
#include<queue>
 
#define endl "\n"
#define MAX 100000
using namespace std;
 
int N, K;
int MAP[2][MAX];
bool Visit[2][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < 2; i++)
    {
        string Inp; cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            MAP[i][j] = Inp[j] - '0';
        }
    }
}
 
void BFS()
{
    bool Flag = false;
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(0, 0), 0));    // x, y, time
    Visit[0][0] = true;
 
    while (Q.empty() == 0 && Flag == false)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Time = Q.front().second;
        Q.pop();
 
        if (Time >= N) break;
 
        for (int i = 0; i < 2; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (ny >= N) Flag = true;
 
            if (nx >= 0 && ny > Time && nx < 2 && ny < N)
            {
                if (MAP[nx][ny] == 1 && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Time + 1));
                }
            }
        }
 
        for (int i = 2; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i] + K;
            
            if (ny >= N) Flag = true;
 
            if (nx >= 0 && ny > Time && nx < 2 && ny < N)
            {
                if (MAP[nx][ny] == 1 && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Time + 1));
                }
            }
        }
    }
 
    if (Flag == true) cout << 1 << endl;
    else cout << 0 << endl;
}
 
void Solution()
{
    BFS();
}
 
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;
}