BOJ 13565 - 침투

문제

백준 온라인 저지 - 13565번

풀이 과정

섬유의 바깥쪽에서 안쪽으로 침투가 가능한지 판단하는 BFS 문제입니다.

0번째 행에서 시작해서 M-1 번째 행에 도달 가능한지 판단하면 됩니다.

코드

import sys
from collections import deque

M, N = list(map(int, sys.stdin.readline().split()))
board = [list(sys.stdin.readline().strip()) for _ in range(M)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def in_range(x, y):
    return 0 <= x < M and 0 <= y < N


def bfs(visit, x, y):
    q = deque()

    visit[x][y] = 1
    q.append([x, y])

    while q:
        x, y = q.popleft()
        if x == M - 1:
            return True

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if in_range(nx, ny) and not visit[nx][ny] and board[nx][ny] == '0':
                visit[nx][ny] = 1
                q.append([nx, ny])

    return False


def solution():
    percolate = False
    visit = [[0] * N for _ in range(M)]

    for y in range(N):
        if not visit[0][y]:
            percolate = bfs(visit, 0, y)
            if percolate:
                break

    return 'YES' if percolate else 'NO'


print(solution())