13565: 침투

• toc {:toc}

문제 확인하기

풀이

outer side에서 inner side로 이동하는 상황을 가정하기 위해서 1행의 전기가 통하는 부분만 큐에 집어 넣는다. BFS를 이용해서 탐색하고 탐색하는 동안 마지막 행에 도달하면 inner side로 나갈 수 있기 때문에 마지막 행에 도달할 경우 YES를 출력하고 프로그램을 종료한다.
while 문이 끝나는 동안에도 프로그램이 종료되지 않는 경우는 마지막 행에 도달하지 않은 것이기 때문에 NO를 출력하고 프로그램을 종료한다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
 
int board[1003][1003];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
queue <pair<int, int>> q;
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    int M, N;
 
    cin >> M >> N;
    
    for(int i = 0; i < M; i++){
        for(int j = 0; j < N; j++){
            char ch;
            cin >> ch;
            if(ch == '0') board[i][j] = 0;
            else board[i][j] = 1;
 
            if(i == 0 && board[i][j] == 0){
                board[i][j] = -1;
                q.push({i, j});
            }
        }
    }
 
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        for(auto dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
            if(board[nx][ny] == -1 || board[nx][ny] == 1) continue;
            if(nx == M-1){
                cout << "YES" << endl;
                return 0;
            }
            q.push({nx, ny});
            board[nx][ny] = -1;
        }
    }
 
    cout << "NO" << endl;
 
    return 0;
}