백준 15558 점프 게임

문제 링크

단순 구현 문제이다.

BFS로 모든 경로를 탐색하면 된다.

방문 처리를 통해 방문했던 노드를 방문하는 것을 방지하면 최대 20만번 탐색하기 때문에 시간초과가 나지 않는다.

#include<bits/stdc++.h>

using namespace std;

int N, k;
string tiles[2];
bool visited[2][100'001];

struct INFO{
    int x, y, t;

    INFO(int x, int y, int t) : x(x), y(y), t(t){}
};

int flipflop(int a){
    if(a==0) return 1;
    return 0;
}

int main(){
    cin >> N >> k >> tiles[0] >> tiles[1];
    for(int i = 0; i < k;i++){
        tiles[0].push_back('1');
        tiles[1].push_back('1');
    }
    //BFS
    bool flag = false;
    queue<INFO> q;
    q.push(INFO(0,1,0));
    visited[0][1] =true;

    while(!q.empty()){
        int cur_x = q.front().x;
        int cur_y = q.front().y;
        int cur_t = q.front().t;
        // cout << cur_x << " " << cur_y << " " << cur_t << endl;
        q.pop();
        if(cur_y > N){
            flag = true;
            break;
        }
        int ff_x = flipflop(cur_x);
        if(tiles[cur_x][cur_y] == '1' && !visited[cur_x][cur_y + 1]) {
            q.push(INFO(cur_x, cur_y+1, cur_t + 1));
            visited[cur_x][cur_y+1] = true;
        }
        if(tiles[cur_x][cur_y - 2] == '1' && cur_y - 2 > cur_t && !visited[cur_x][cur_y - 1]) {
            q.push(INFO(cur_x, cur_y-1, cur_t + 1));
            visited[cur_x][cur_y-1] = true;
        }
        if(tiles[ff_x][cur_y + k - 1] == '1' && !visited[ff_x][cur_y + k]) {
            q.push(INFO(ff_x, cur_y + k, cur_t + 1));
            visited[ff_x][cur_y+k] = true;
        }
    }
    if(flag)cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}