문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

from collections import deque

m, n = map(int, input().split())
graph = []
for _ in range(m):
  graph.append(list(map(int, input())))

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


def bfs(x, y=0):
  visited = [[False] * n for _ in range(m)]
  queue = deque()
  queue.append((x, y))
  while queue:
    x, y = queue.popleft()
    if graph[y][x] == 0:
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
          continue
        if graph[ny][nx] == 0 and visited[ny][nx] == False:
          queue.append((nx, ny))
          visited[ny][nx] = True
    if y == (m - 1) and graph[y][x] == 0:
      check[0] = "YES"


check = ["NO"]
for i in range(n):
  bfs(i)
  if check[0] == "YES":
    break

print(check[0])

백준 13565 침투