[13565] 침투

https://www.acmicpc.net/problem/13565

13565번: 침투

<문제>

0행중 '0'인것을 큐에 전부 넣고, bfs를 돌린 뒤 n-1행중 방문한 정점이 있는지를 체크하면 된다.

0행이 비어있다면 어떻게든 전류가 바깥쪽에서 공급될 수 있고

n-1행이 비어있다면 어떻게든 전류가 안쪽까지 도달할 수 있다.

bfs의 시작조건, 전류의 전달되는 부분에대한 모델링만 잘 이루어지면 간단한 bfs문제로 바꿔풀 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
char a[1005][1005];
bool visited[1005][1005];
int main(void) {
    cin >> n >> m;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) cin >> a[i][j];
    queue<pair<int, int>> q;
    for (j = 0; j < m; j++) {
        if (a[0][j] == '0') {
            q.push({0, j});
            visited[0][j] = true;
        }
    }
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            int y = cur.first + dy[i];
            int x = cur.second + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == '0' && visited[y][x] == false) {
                visited[y][x] = true;
                q.push({y, x});
            }
        }
    }
    bool flag = false;
    for (j = 0; j < m; j++)
        if (visited[n - 1][j]) flag = true;
    cout << (flag ? "YES" : "NO");
    return 0;
}