Codeforces Round #614 (Div.2 ) C. NEKO's Maze Game

미로 찾기 문제입니다. (1,1)에서 시작하여 (2,n)으로 갈 수 있으면 Yes, 없으면 No를 출력합니다.

용암이 있는 길을 갈 수 없으며, 용암은 인풋으로 주어집니다. 용암은 토글 형식이고 같은 좌표가 2번 들어오면 용암을 없어집니다.

처음에는 DFS로 문제를 풀어봤는데, memory가 부족해서 통과하지 못했습니다.

그래서 막힌 길의 개수를 저장하고, 막힌 길의 개수가 0이면 Yes를 출력하도록 코드를 작성했습니다.

예를 들어, (2,3)에 용암이 있을 때 (1,4), (1,3), (1,2) 에 용암이 생긴다면 길이 막히게 됩니다.

1,5	2.5
1,5	2.5
1,4 (후보)	2,4
1,3 (후보)	2,3 (용암)
1,2 (후보)	2,2
1,1	2,1

따라서, 용암이 생길 때 반대편 3군데의 길을 보고 용암이 있으면 +1를 해주고, 반대로 용암이 없어질 때는 -1을 해주면 막힌 길을 셀 수 있습니다.

#include <iostream>
#include <stack>
 
using namespace std;
 
int maze[2][100010]; 
int n, q;
 
int main(){
    
    cin >> n >> q;
 
    for (int i = 0; i < 2; i ++){
        for (int j = 0; j < 100010; j ++){
            //미로 초기화 : 0이면 갈 수 있는 길, 1이면 용암.
            maze[i][j] = 0;
        }
    }
    mazeRecord[0][n] = 1;
    mazeRecord[1][n] = 1;

    int numBlocked = 0;
    int x, y;
    for (int i = 0; i < q; i ++){
        cin >> x >> y;
        
        int nextX = 1 - (x - 1);
        int nextY = y;

        for (int a = y -2; a <= y; a ++){
            if (a < 0){
                continue;
            } 
            if (a >= n){
                continue;
            }
            //용암이 없어지는 경우
            if(maze[x-1][y-1] == 1){
                if(maze[nextX][a] == 1){
                    numBlocked --;
                }
                //용암이 생기는 경우
            } else if (maze[x-1][y-1] == 0){
                if(maze[nextX][a] == 1){
                    numBlocked ++;
                }
            }
        
        }
        maze[x-1][y-1] = 1 - maze[x-1][y-1]; // 0, 1 토글 시킴

        if(numBlocked == 0){
            cout << "Yes" << endl;
        } else{
            cout << "No" << endl;
        }
    }
    return 0;
}