[백준 Python] 13565번 침투

백준 파이썬 13565번 침투

Silver 2

 

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

import sys
input = sys.stdin.readline
from collections import deque
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def bfs():
    while q:
        y, x = q.popleft()
        for tx, ty in move:
            dx = x + tx
            dy = y + ty
            if 0 <= dx < n and 0 <= dy < m and not visited[dy][dx] and lst[dy][dx] == '0':
                if dy == m-1:
                    return "YES"
                visited[dy][dx] = True
                q.append((dy, dx))
    return "NO"
m, n = map(int, input().split())
lst = []
visited = [[False]*n for _ in range(m)]
for i in range(m):
    lst.append(input().rstrip())
q = deque()
for j in range(n):
    if lst[0][j] == '0':
        q.append((0, j))
print(bfs())

 

lst[0][idx] 에서 lst[m-1][idx] 에 도달할 수 있는지 확인하는 문제로 bfs를 이용해 문제를 풀 수 있다.