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

문제

https://www.acmicpc.net/problem/15558

접근 방법

3가지 이동은 가중치가 동등한 이동입니다. 특정 칸은 늦게 도착할 시 칸이 없어질 수 있기에 최대한 빠르게 도착한 이동을 우선해 주어야 합니다.

코드

#include <iostream>
#include <queue>
using namespace std;

struct node
{
    int y, x, time;
};

int N, k;
string map[2];
bool isVisited[2][100000];
queue<node> q;

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> k;
    for (int i = 0; i < 2; ++i)
    {
        cin >> map[i];
    }
}

bool push(node nextNode)
{
    if (nextNode.x >= N)
    {
        return true;
    }

    if (isVisited[nextNode.y][nextNode.x])
    {
        return false;
    }

    if (map[nextNode.y][nextNode.x] == '0')
    {
        return false;
    }

    if (nextNode.time > nextNode.x)
    {
        return false;
    }

    isVisited[nextNode.y][nextNode.x] = true;
    q.push(nextNode);

    return false;
}

bool isClearable()
{
    q.push({0, 0, 0});

    while (!q.empty())
    {
        node curNode = q.front();
        q.pop();

        if (push({(curNode.y + 1) % 2, curNode.x + k, curNode.time + 1}) ||
            push({curNode.y, curNode.x + 1, curNode.time + 1}) ||
            push({curNode.y, curNode.x - 1, curNode.time + 1}))
        {
            return true;
        }
    }

    return false;
}

int main()
{
    input();
    cout << isClearable();
    return 0;
}

풀이

BFS를 활용합니다. 가중치가 동등하기에 가장 먼저 도착한 경우가 가장 빠르게 도착하다고 할 수 있습니다.
이동하려는 위치가 N을 넘는 경우 게임을 클리어할 수 있고 이미 방문했거나 사라졌거나 위험한 칸인 경우에는 사용하면 안 되는 이동이기에 무시해 줍니다.