[백준] 15806 영우의 기숙사 청소

영우는 바쁘다. 기숙사 청소를 해야하는지 알려줘야 한다

BFS 그냥 돌리면 시간초과가 난다..!

그냥 돌리면 방문한 곳을 다음에 다시 또 방문하게된다!

방법은 바로 이전에 방문한 곳을 체크해 두고 방문 안했을 경우에만 큐에 넣는다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int arr[333][333];
bool check[333][333][2];
int n, m, k, t;
int dx[8] = { -1,-2,-2,-1,1,2,2,1 };
int dy[8] = { -2,-1,1,2,-2,-1,1,2 };
 
vector<pair<int, int>> clean;
int main() {
    scanf(" %d %d %d %d", &n, &m, &k, &t);
    clean.resize(k);
 
    queue<pair<int, int>> q;
    for (int i = 0; i < m; i++) {
        int x, y; scanf(" %d %d", &y, &x);
        x--; y--;
        arr[x][y] = 1;
        check[x][y][0] = 1;
        q.push({ x,y });
    }
 
    for (int i = 0; i < k; i++) {
        int x, y; scanf(" %d %d", &y, &x);
        x--; y--;
        clean[i] = { x,y };
    }
 
    int cnt = 0;
    while (t--) {
        int s = q.size();
        while (s--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            check[x][y][cnt] = false;
 
            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (!check[nx][ny][(cnt+1) % 2]) {
                        check[nx][ny][(cnt+1) % 2] = true;
                        q.push({ nx,ny });
                    }
                }
            }
        }
        cnt++;
    }
    for (int i = 0; i < k; i++) {
        int x = clean[i].first;
        int y = clean[i].second;
        if (check[x][y][cnt%2]) {
            puts("YES"); return 0;
        }
    }
    puts("NO");
}