BOJ 13565 · 침투

알고리즘 분류 : BFS  

바깥쪽부터 안쪽까지 전류가 침투할 수 있는지 확인하는 것을 구현해야 한다. 바깥쪽은 첫 번째 행이며, 안쪽은 마지막 행이다. 첫 번째 행부터 BFS 탐색을 시작해서 마지막 행에 도달하는지 확인해보면 된다.

• 0 번째 행에 있는 모든 흰색 격자(0)의 좌표를 큐에 집어넣는다.
• BFS 탐색을 시작하여 N 번째 행까지 도달하는지 확인한다. 차단 물질(1)로는 이동할 수 없다.
• N-1 번째 행에 도달하면 전류가 침투 가능한 것이므로 "YES"를 출력하고 탐색을 종료한다.
• BFS 탐색이 끝날 때까지 N-1 번째 행에 도달하지 못하면, 침투 불가능한 것이므로 "NO"를 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct grid {
    int x, y;
};

int n, m;
char a[1001][1001];
bool check[1000][1000];
queue<grid> q;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs() {
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        if (x == n-1) {
            printf("YES\n");
            return;
        }
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || ny < 0 || ny >= m) continue;
            if (!check[nx][ny] && a[nx][ny] == '0') {
                q.push({nx, ny});
                check[nx][ny] = true;
            }
        }
    }
    printf("NO\n");
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        scanf("%s", a[i]);
    }
    for (int j=0; j<m; j++) {
        if (a[0][j] == '0') {
            q.push({0, j});
            check[0][j] = true;
        }
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

from collections import deque
from sys import stdin
input = stdin.readline

def bfs():
    while q:
        x, y = q.popleft()
        if x == n-1:
            print("YES")
            return
        for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or ny < 0 or ny >= m:
                continue
            if not check[nx][ny] and a[nx][ny] == '0':
                q.append((nx, ny))
                check[nx][ny] = True
    print("NO")

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
check = [[False]*m for _ in range(n)]
q = deque()
for j in range(m):
    if a[0][j] == '0':
        q.append((0, j))
        check[0][j] = True
bfs()

---

참고

• 백준 온라인 저지 : BOJ 13565