[백준] 15558 점프 게임

 

숨바꼭질? 그 문제랑 비슷한 문제다

내가 갈 수 있는 경우를 다 큐에 넣고 bfs를 돌리면 된다

 

이 때 시간마다 칸이 사라지므로 그 경우를 큐의 사이즈를 통해 해결하자!

 

평소처럼 큐가 비어있으면 돌리는게 아닌 현재 시간에 갈 수 있는 만큼만 큐를 돌리는거다

현재 시간에 움직일 수 있는 칸  == 현재 큐 사이즈 이용 ㄱㄱ

 

문제를 잘 읽어보면 N번 칸 보다 더 큰 칸으로 간다면 1이므로 조건을 잘 확인하자!

 

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, k,ans;
int map[100010][2];
bool check[100010][2];
int dx[2] = { 1,-1 };
int dy[2] = { 0,0 };
 
bool inner(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < 2);
}
int main() {
    scanf(" %d %d", &n, &k);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            scanf(" %1d", &map[j][i]);
        }
    
    }
 
    queue<pair<int, int>> q;
    q.push({ 0,0 });
    check[0][0] = true;
    int _time = 0;
    while (int s = q.size()) {
        while (s--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            if (x < _time) continue;
 
            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (inner(nx, ny) && map[nx][ny] == 1 && !check[nx][ny]) {
                    check[nx][ny] = true;
                    q.push({ nx,ny });
                }
            }
 
            int nx = x + k;
            int ny = (y + 1) % 2;
            if (inner(nx, ny) && map[nx][ny] == 1 && !check[nx][ny]) {
                check[nx][ny] = true;
                q.push({ nx,ny });
            }
            else if (nx >= n) ans = 1;
        }
        _time++;
    }
 
    ans = ans || check[n - 1][0] || check[n - 1][1];
    printf("%d\n", ans);
 
    
}